Traversée d'un arbre pour trouver un nœud

Question

Je cherche dans un arbre pour trouver une valeur qui est passée. Malheureusement ça ne marche pas. J'ai commencé à le déboguer avec des impressions, et ce qui est bizarre, c'est qu'il trouve la valeur, mais ignore l'instruction return.

/** 
    * Returns the node with the passed value 
    */ 
private TreeNode searchNodeBeingDeleted(Comparable c, TreeNode node) 
{ 
    if(node == null) 
    { 
    return null; 
    } 

    if(c.equals((Comparable)node.getValue())) 
    { 
    System.out.println("Here"); 
    return node; 
    } 
    else 
    { 
    if(node.getLeft() != null) 
    { 
    System.out.println("left"); 
    searchNodeBeingDeleted(c, node.getLeft()); 
    } 
    if(node.getRight() != null) 
    { 
    System.out.println("right"); 
    searchNodeBeingDeleted(c, node.getRight()); 
    } 
    } 
    return null; //i think this gives me my null pointer at bottom 
} 

Il imprime les résultats comme suit:

left 
left 
right 
right 
Here 
right 
left 
right 
left 
right 
Exception in thread "main" java.lang.NullPointerException 
at Program_14.Driver.main(Driver.java:29) 

Je ne sais pas si cela va aider, mais voici mon arbre:

 L 
/ \ 
    D  R 
/\ /\ 
A F M U 
\  /\ 
    B  T V 

Merci pour votre temps.

Answer 1

Essayez ceci:

private TreeNode searchNodeBeingDeleted(Comparable c, TreeNode node) 
{ 
    if(node == null) 
    { 
    return null; 
    } 

    if(c.equals((Comparable)node.getValue())) 
    { 
    System.out.println("Here"); 
    return node; 
    } 
    else 
    { 
    if(node.getLeft() != null) 
    { 
    System.out.println("left"); 
    TreeNode n = searchNodeBeingDeleted(c, node.getLeft()); 
    if (n != null) { 
     return n; 
    } 
    } 
    if(node.getRight() != null) 
    { 
    System.out.println("right"); 
    TreeNode n = searchNodeBeingDeleted(c, node.getRight()); 
    if (n != null) { 
     return n; 
    } 
    } 
    } 
    return null; //i think this gives me my null pointer at bottom 
} 

Answer 2

Je pense que vous devez retourner la valeur de searchNodeBeingDeleted(c, node.getLeft()) et searchNodeBeingDeleted(c, node.getRight()), et pas seulement appeler ces méthodes.

Answer 3

Vous utilisez la récursivité dans votre fonction. Le 'ici' que vous voyez est le résultat d'un appel de fonction qui a été créé à partir de la même fonction. Donc, il va retourner une valeur à la fonction 'récursive', à ce stade, vous n'avez pas encore terminé, même si vous avez trouvé la réponse, vous devez toujours continuer à la propager vers le haut.

Answer 4

En supposant que votre arbre est un binary search tree et non un "regular" binary tree.

Vous devriez retourner vos appels récursifs et ne pas retourner null à la fin de votre méthode.

Quelque chose comme ceci:

private TreeNode searchNodeBeingDeleted(Comparable c, TreeNode node) { 
    if(nodle == null) return null; 
    int diff = c.compareTo((Comparable)node.getValue()); 
    if (diff == 0) { // yes, we found a match! 
     System.out.println("Here"); 
     return node; 
    } 
    else if (diff < 0) { // traverse to the left 
     System.out.println("left"); 
     return searchNodeBeingDeleted(c, node.getLeft()); 
    } 
    else { // traverse to the right 
     System.out.println("right"); 
     return searchNodeBeingDeleted(c, node.getRight()); 
    } 
}