Двоичное дерево поиска, реализованное в Java - поиск элемента рекурсивно

Question

Использование Java, можно ли написать рекурсивный метод для поиска элемента в двоичном дереве поиска? Я говорю «нет» из-за характера рекурсивного повторного трассировки, если я не выполнил неправильно? Я искал в Интернете, и все, что я могу найти, это итеративная версия. Вот мой метод:

public boolean findValueRecursively(BSTNode node, int value){ 
    boolean isFound = false; 
    BSTNode currentNode = node; 

    if (value == currentNode.getData()){ 
     isFound = true; 
     return isFound; 
    } else if (value < currentNode.getData()){ 
     findValueRecursively(currentNode.getLeftNode(), value); 
    } else{ 
     findValueRecursively(currentNode.getRightNode(), value); 
    } 

    return isFound; 
} 

// Node data structure 
public class BSTNode 
{ 
    private BSTNode leftNode; 
    private BSTNode rightNode; 
    private int data; 
    public BSTNode(int value, BSTNode left, BSTNode right){ 
     this.leftNode = left; 
     this.rightNode = right; 
     this.data = value; 
    } 
} 



public static void main(String[] args){ 
    BST bst = new BST(); 
    // initialize the root node 
    BSTNode bstNode = new BSTNode(4, null, null); 
    bst.insert(bstNode, 2); 
    bst.insert(bstNode, 5); 
    bst.insert(bstNode, 6); 
    bst.insert(bstNode, 1); 
    bst.insert(bstNode, 3); 
    bst.insert(bstNode, 7); 
    if (bst.findValueRecursively(bstNode, 7)){ 
     System.out.println("element is found! "); 
    } else{ 
     System.out.println("element is not found!"); 
    } 
} 

Я получаю печать как «элемент не найден».

Любая помощь/советы или предложения, более чем приветствуются.

Заранее благодарен!

Answer 1

Рекурсивная версия:

public boolean findValueRecursively(Node node, int value){ 
     if(node == null) return false; 
     return 
       node.data == value || 
       findValueRecursively(leftNode, value) || 
       findValueRecursively(rightNode, value); 
    } 

Answer 2

рекурсивная версия, которая возвращает ссылку на узел найден:

public BinaryNode find(BinaryNode node, int value) { 
    // Finds the node that contains the value and returns a reference to the node. 
    // Returns null if value does not exist in the tree.     
    if (node == null) return null; 
    if (node.data == value) { 
     return node; 
    } else { 
     BinaryNode left = find(node.leftChild, value); 
     BinaryNode right = find(node.rightChild, value); 
     if (left != null) { 
      return left; 
     }else { 
      return right; 
     } 
    } 
} 

Answer 3

Я считаю, ваш isFound = false; это то, что всегда возвращается.

Это должно быть так:

isFound= findValueRecursively(currentNode.getLeftNode(), value);