So finden Sie einen Knoten in einem binären Suchbaum

Question

Ich las über binäre Bäume in Java. Ich fand diesen Code:

public BSTNode findNode(Comparable val){ 
     int delta = val.compareTo(value); 
     // the value is less than this.value 
     if(delta < 0){ 
      // if there is a leftChild, return left.findNode(val) 
      // there is no leftChild, so the val does not exist 
      // in the node, so return null 
      return (left!= null)? left.findNode(val): null; 
     } 
     // else if the value is greater than this.value 
     else if (delta > 0){ 
      // if there is a rightChild, then return right.findNode(val) 
      // else, there is no rightChild, return null 
      return (right != null)? right.findNode(val): null; 
     } 
     // else, dela == 0, so we have found the node with that 
     // val, return the node 
     return this; 
    } 

Ich verstehe nicht, wie das funktioniert:

return (left!= null)? left.findNode(val): null; 
return (right != null)? right.findNode(val): null; 

Können Sie es in einer anderen Art und Weise neu zu schreiben?

Dank

Answer 1

OK, gehen wir Schritt für Schritt. Zunächst konzentriere ich mich auf den Algorithmus selbst.

class Node<T> { 
    T value; 
    Node left; 
    Node right; 
} 

Sie garantiert werden, dass alle Werte auf die left sind kleiner oder gleich als value und alle Werte auf die right sind größer oder gleich als value. Dies erleichtert die Suche. Wenn Sie nach Element val suchen, vergleichen Sie es einfach mit dem value in aktuellen Node. Wenn das gewünschte Element das gleiche aktuelle Element ist, haben Sie es gefunden. Wenn es größer ist, kann es nur im rechten Teil eines Baumes sein. Sonst auf der linken Seite.

Es kann vorkommen, dass das Element nicht hier ist. Es passiert, wenn Sie sehen, dass es links/rechts vom aktuellen Knoten sein sollte, aber dort ist nichts (null).

So ist die BinaryTreeSearch ist:

T search(Node tree, T val) { 
    int delta = tree.getValue.compareTo(val); 
    if (delta == 0) { 
     return tree.getValue; 
    } else if (delta > 0) { 
     return search(tree.getRight(), val); 
    } else { 
     return search(tree.getLeft(), val); 
    } 
} 

Aber warten ... dies auf die NPE führt, wenn das Element nicht hier ist. Lassen Sie uns es ändern:

T search(Node tree, T val) { 
    if (tree == null) 
     return null; 
    int delta = tree.getValue.compareTo(val); 
    if (delta == 0) { 
     return tree.getValue; 
    } else if (delta > 0) { 
     return search(tree.getRight(), val); 
    } else { 
     return search(tree.getLeft(), val); 
    } 
} 

Dies kann auch auf diese Weise neu geschrieben werden:

T search(Node tree, T val) { 
    int delta = tree.getValue.compareTo(val); 
    if (delta == 0) { 
     return tree.getValue; 
    } else if (delta > 0) { 
     if (tree.getRight() == null) 
      return null; 
     return search(tree.getRight(), val); 
    } else { 
     if (tree.getLeft() == null) 
      return null; 
     return search(tree.getLeft(), val); 
    } 
} 

Aber hier kommt der ternäre Operator, verkürzt und vereinfacht if-else.

result = testCondition ? value1 : value2 

die die gleichen wie

if (testCondition) { 
    result = value1; 
} else { 
    result = value2; 
} 

Ein weiter Operator ist:?, Die für eine if-then-else-Anweisung (besprochen in der Kontrollflussrechnung als Kürzel gedacht werden kann Abschnitt dieser Lektion). Dieser Operator wird auch als ternärer Operator bezeichnet, da er drei Operanden verwendet. Im folgenden Beispiel sollte dieser Operator wie folgt gelesen werden: "Wenn acoDition true ist, weisen Sie result den Wert von value1 zu. Andernfalls weisen Sie den Wert von value2 result zu."

So erhalten wir schließlich:

T search(Node tree, T val) { 
    int delta = tree.getValue.compareTo(val); 
    if (delta == 0) { 
     return tree.getValue; 
    } else if (delta > 0) { 
     return (tree.getRight() == null) ? null : search(tree.getRight(), val); 
    } else { 
     return (tree.getLeft() == null) ? null : search(tree.getLeft(), val); 
    } 
} 

Answer 2

Sie können wie folgt umgeschrieben werden:

hilft

if(left != null) { 
    return left.findNode(val); 
} else { 
    return null; 
} 

und

if(right != null) { 
    return right.findNode(val); 
} else { 
    return null; 
} 

Hope this :-).