Binärbaum rekursiv suchen

Question

Hallo Ich habe Probleme, diesen Code richtig zu funktionieren. Es scheint aus dem Stapel herauszuspringen, wenn es den gesamten linken Rand des Baumes zurückspringt. Ich kann es einfach nicht verstehen.

public static Node lookup(Node node, int lookupValue) { 

     if (node == null) { 
      return null; 
     } else { 
      if (node.value == lookupValue) { 
       System.out.println("Found"); 
       return node; 
      } else if(node.left != null) { 
       return lookup(node.left, lookupValue); 

      } else if(node.right != null) { 
       return lookup(node.right, lookupValue); 
      } else { 
       return null; 
      } 
     } 
} 

Answer 1

Sie geben zurück, was aus dem linken Teilbaum (falls vorhanden) zurückgegeben wird, ohne den richtigen zu überprüfen. Ein Großteil der Verzweigung else ist nicht erforderlich, wenn eine return Anweisung im if Block vorhanden ist. Ändern Sie wie folgt vor:

public static Node lookup(Node node, int lookupValue) { 
    if (node == null) 
     return null; 
    if (node.value == lookupValue) 
     // System.out.println("Found"); 
     return node; 
    Node rval = lookup(node.left, lookupValue); 
    // only return if found in left sub-tree 
    return (rval != null) ? rval : lookup(node.right, lookupValue); 
} 

Answer 2

Ihre else if sind nicht korrekt Sie chould die linken und rechten Jederzeit gerne überprüfen:

if (node == null) return null; 
if (node.value == lookupValue) { 
    System.out.println("Found"); 
    return node; 
} 
Node found = lookup(node.left, lookupValue); 
if(found != null) { 
    return found; 
} 
return lookup(node.right, lookupValue);