Arbre de recherche binaire implémenté en Java - Recherche élémentaire récursivement

Question

En utilisant Java, est-il possible d'écrire une méthode récursive pour trouver un élément dans un arbre de recherche binaire? Je dis non en raison de la nature de re-tracer récursif à moins que je ne l'ai pas mis en œuvre correctement? J'ai cherché sur Internet et tout ce que je peux trouver est une version itérative. Voici ma méthode:

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!"); 
    } 
} 

Je reçois l'impression comme "élément n'est pas trouvé".

Toute aide/conseils ou suggestions, plus que bienvenue.

Merci d'avance!

Answer 1

Une version récursive:

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

Answer 2

Une version récursive qui renvoie une référence au nœud trouvé:

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

Je crois que votre isFound = false; est ce qui est toujours retourné.

Il devrait ressembler à ceci:

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