이진 검색 트리에서 값을 찾는 데 필요한 반복 횟수를 표시 (출력)하는 방법은 무엇입니까?

Question

이 프로그램을 작성하여 BST를 만들었습니다. 사용자가 트리를 만들고 BST에서 값을 검색 할 수 있지만이 번호를 찾는 데 필요한 반복 횟수를 출력하는 데 도움이 필요합니다. 어떻게하는지. "iterations"라는 변수를 만들었지 만이 숫자를 수집하는 방법을 만드는 방법으로 붙어 있습니다. 모든 아이디어를 내 프로그램에서 어떻게 구현할 것인가, 그 번호를 찾아서 인쇄하는 방법은 무엇입니까?

import java.util.Scanner; 


/* 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(); 

} 

} 

Answer 1

iterations이라는 전역 변수는 처음에는 0입니다.

그런 다음 모든 방법의 루프에서 iterations을 증가 시키십시오. 모든 방법을 시작할 때 iterations을 0으로 재설정해야합니다.

그런 다음 반복을 반환 getLastIterationCount라는 방법을 쓰기 :

public int getLastIterationCount(){ 
    return iterations; 
} 

당신이 사용되었다 얼마나 많은 반복을 알아 getIterationCount()를 호출하고 결과를 인쇄 할

. 예를 들어,) (예약 주문 걸리는 많은 반복 볼이 쓰기 :

/* Class BST */ 
class BST 
{ 
private Node root; 
private int iterations; 

... 

    /* 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; 
    ... 
    return found; 
} 

public int getLastIterationCount(){ 
    return iterations; 
} 

} 

Answer 2

이 두 멤버를 포함 SearchResult라는 도우미 클래스를 정의

여기

preorder(...); 
System.out.println(bst.getLastIterationCount()); 

이처럼 BST 클래스 보일 수 있습니다 것입니다 : found 및 iterations.

search(..) 메서드가 boolean 대신이 클래스를 반환하는지 확인하십시오.

Answer 3

iterations = 1로 설정 한 다음 나중에 증가시키고 bst 클래스에있는 메소드이므로 'getLastIterationCount()'가 아닌 'bst.getLastIterationCount()'를 사용하여 출력해야합니다.