2017-12-13 2 views
0

이진 검색 트리 (사용자 입력 사용)를 구현하고 값을 검색하여 실제로이 값을 찾는 데 필요한 반복 횟수를 출력하는 프로그램을 만들 수없는 것처럼 보입니다. 반복 수를 반환하는 getLastIterationCount()라는 메서드를 만들었지 만 주 메서드에서 인쇄하려고 할 때 'System.out.println (getLastIterationCount())'줄에 오류가 발생합니다. ; '. 내 방법이 올바른 위치에 있지 않다고 생각하지만 실종 된 것이 확실하지 않습니다. 어떻게하면이 프로그램을 만들 수있는 아이디어가 있습니까?BST에서 값을 찾는 데 필요한 반복 횟수를 출력하는 방법은 무엇입니까?

 /* Class Node */ 
class Node 


{ 
Node left, right; 
int data; 



/* Constructor */ 
public Node(int n) 
{ 
    left = null; 
    right = null; 
    data = n; 
}   

/* Function to get data from node */ 
public int getData() 
{ 
    return data; 
} 

/* Function to get left node */ 
public Node getLeft() 
{ 
    return left; 
} 

/* Function to get right node */ 
public Node getRight() 
{ 
    return right; 
    } 
} 

/* Class BST */ 
class BST 

{ 

private Node root; 
private int iterations; 
/* Constructor */ 
public BST() 
{ 
    root = null; 
} 
/* Functions to insert data */ 
public void insert(int data) 
{ 
    root = insert(root, data); 
} 
/* Function to insert data recursively */ 
private Node insert(Node node, int data) 
{ 
    if (node == null) 
     node = new Node(data); 
    else 
    { 
     if (data <= node.data) 
      node.left = insert(node.left, data); 
     else 
      node.right = insert(node.right, data); 
    } 
    return node; 
} 


    /* Functions to search for an element */ 
public boolean search(int val) 
{ 
    iterations=0; 
    iterations++; 
    return search(root, val); 
} 



/* Function to search for an element recursively */ 
private boolean search(Node r, int val) 
{ 
    iterations=0; 
    boolean found = false; 
    while ((r != null) && !found) 
    { 
     int rval = r.getData(); 
     if (val < rval){ 
      r = r.getLeft(); 
     } 

     else if (val > rval){ 
      r = r.getRight(); 
     } 

     else 
     { 
      found = true; 
      break; 
     } 
     found = search(r, val); 

    } 

    return found; 
} 

    public int getLastIterationCount(){ 
    return iterations; 
    } 


    } 
    /* Class LinkedListBST */ 
    public class LinkedListBST 
    { 


public static void main(String[] args) 

{ 


    Scanner scan = new Scanner(System.in); 
    /* Creating object of BST */ 
    BST bst = new BST(); 
    System.out.println("Linked List Binary Search Tree Test\n");   
    char ch; 
    /* Accept input */ 
    do  
    { 
     System.out.println("Enter integer element to insert"); 
     bst.insert(scan.nextInt());      



     System.out.println("\nDo you want to continue (Type y or n) \n"); 
     ch = scan.next().charAt(0); 


    } while (ch == 'Y'|| ch == 'y'); 
    System.out.println("\nEnter an element to be searched: "); 
    Scanner sc = new Scanner(System.in); 
    System.out.println("Search result : " + bst.search(sc.nextInt())); 

    System.out.println(getLastIterationCount()); //ISSUE IS HERE 

    sc.close(); 

    } 

    } 

답변

0

검색 코드가 이미 정확하다고 생각합니다. 하나를 사용하여 카운터를 증가,

public boolean search(int val) { 
    iterations = 1; 
    return search(root, val); 
} 

을 그리고, 민간 내부 검색 방법에 대한 각 호출에 : 첫째, 검색 할 외부 진입 점에서 카운터를 초기화 내가 여기에 가정 한

private boolean search(Node r, int val) { 
    ++iterations;  // increment counter by one for current iteration 

    boolean found = false; 
    while ((r != null) && !found) { 
     int rval = r.getData(); 
     if (val < rval){ 
      r = r.getLeft(); 
     } 
     else if (val > rval) { 
      r = r.getRight(); 
     } 
     else { 
      found = true; 
      break; 
     } 

     found = search(r, val); 
    } 

    return found; 
} 

을 그 값을 찾는 데 필요한 재귀 호출 수가 필요합니다. 대신에 항목이 발견 된 높이를 원한다면 다른 질문입니다.

편집 :

난 당신이 수를 반환하는 getter 메소드를 가지고 것으로 나타났습니다. 그것은 인스턴스 메서드이고 당신은 그러므로 같은 호출한다 : 당신은 방법 getLastIterationCount()에 액세스하는

bst.getLastIterationCount(); 
+0

나는 당신의 충고에 따라, 고마워하지만 내 'System.out.println (getLastIterationCount());' Netbeans에 의해 잘못된 것으로 밑줄이 그어져 있습니다. 내 메소드 'getLastIterationCount()'가 잘못된 위치에있어 내 print 문이 함수 호출을 인식하지 못하게합니까? –

+1

안녕하세요 내 대답을보고 그것을 시도하십시오! –

+0

@humanbeing 네, 특정 트리 인스턴스에 대한 카운트를 얻으려면'bst.getLastIterationCount()'를 호출해야합니다. 하지만 더 큰 문제는 계산 논리와 관련이 있다고 생각합니다. –

0

귀하는 다음과 같이 인스턴스화 한 개체 BST를 사용하여 메소드를 호출한다 개체없이. bst.getLastIterationCount()

+0

다른 답변 아래에 의견을 달아 광고를 보내지 마십시오. –

+0

내가 언급 한 문제를 해결하기 위해 나는 그에게 나의 대답을 가르키고 있었다. 나는 광고인지, 나는 관련없는 것을 말하지 않았다는 것을 모른다. –

+0

당신이 옳았지 만 이것은 문제의 일부일뿐입니다. –

1

:

bst.getLastIterationCount() 
관련 문제