Recorrido de un árbol para encontrar un nodo

Question

Estoy buscando a través de un árbol para encontrar un valor que se pasa. Lamentablemente, no funciona. Empecé a depurarlo con impresiones, y lo que es extraño es que realmente encuentra el valor, pero omite la declaración de devolución.

/** 
    * 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 
} 

imprime los resultados de la siguiente manera:

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) 

No sé si esto ayuda, pero aquí es mi árbol:

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

Gracias por su tiempo.

Answer 1

Prueba esto:

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

Creo que debe devolver el valor de searchNodeBeingDeleted(c, node.getLeft()) y searchNodeBeingDeleted(c, node.getRight()), no solo llame a esos métodos.

Answer 3

Está utilizando recursion en su función. El 'aquí' que ves es el resultado de una llamada a función que se ha creado a partir de la misma función. Por lo tanto, devolverá un valor a la función 'recursing', en este punto aún no ha terminado, aunque haya encontrado la respuesta, aún necesita seguir propagándola hacia arriba.

Answer 4

Asumiendo que su árbol es un binary search tree y no un "regular" binary tree.

Debe devolver sus llamadas recursivas y no devolver null al final de su método.

Algo como esto:

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()); 
    } 
}