Przechylanie drzewa w celu znalezienia węzła

Question

Przeszukuję drzewo, aby znaleźć wartość, która została przekazana. Niestety, to nie działa. Rozpocząłem debugowanie go za pomocą odbitek, a co dziwne, faktycznie znajduje wartość, ale pomija instrukcję 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 
} 

To wypisuje wyniki w następujący sposób:

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) 

nie wiem, czy to pomoże, ale tutaj jest moje drzewo:

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

Dzięki za poświęcony czas.

Answer 1

Spróbuj tego:

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

Myślę, że należy zwrócić wartość searchNodeBeingDeleted(c, node.getLeft()) i searchNodeBeingDeleted(c, node.getRight()), a nie tylko wywoływać te metody.

Answer 3

Używasz rekurencji w swojej funkcji. "Tu", który widzisz, jest wynikiem wywołania funkcji, które zostało utworzone z tej samej funkcji. Więc zwróci wartość do funkcji "recursing", w tym momencie jeszcze nie skończyłeś, mimo że znalazłeś odpowiedź, nadal musisz ją propagować w górę.

Answer 4

Zakładając, że drzewo jest binary search tree a nie "regular" binary tree.

Powinieneś zwrócić swoje wywołania rekurencyjne i nie zwracać null na końcu metody.

coś takiego:

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