Binaire un Arbre de Recherche mises en œuvre en Java - Rechercher un Élément de manière récursive

À l'aide de 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 à cause de la nature de récursive re-traçage en arrière, à moins que j'ai mis en œuvre de façon incorrecte? J'ai été chercher sur internet et tout ce que je peux trouver est un processus itératif en version. 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 que "l'élément n'est pas trouvé".

Toute aide/conseils ou des suggestions, plus que la bienvenue.

Merci d'avance!

OriginalL'auteur Allen | 2013-09-21

  1. 8

    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);
    }
    Est-il efficace lorsque nous utilisons un Arbre Énorme avec des milliers de nœud ?
    puisque vous touchez à aucun nœud une fois au plus, je dirais que oui - c'est aussi efficace qu'il obtient. Attention, c'est essentiellement un DFS de numérisation de l'arbre en partant du nœud racine et de descendre.

    OriginalL'auteur alfasin

  2. 2

    Une version récursive qui retourne une référence sur le 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;
        }   
    }
}

    OriginalL'auteur hguochen

  3. 0

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

    Il devrait ressembler à ceci:

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

    OriginalL'auteur Navjot Singh

  4. 0
        public TreeNode<E> binarySearchTree(TreeNode<E> node, E data){
    if(node != null) {
        int side = node.getData().compareTo(data);
        if(side == 0) return node;
        else if(side < 0) return binarySearchTree(node.getRightChild(), data);
        else if(side > 0 ) return binarySearchTree(node.getLeftChild(), data);
    }

    return null;
}

    Qui va renvoyer une référence pour le nœud, ce qui est un peu plus utile IRL. Vous pouvez le changer pour retourner un booléen.

    OriginalL'auteur Juan Pollacchi