algorithm
Prüfen Sie, ob ein Baum BST ist oder nicht

Wenn ein bestimmter Eingabebaum der Eigenschaft "Binärer Suchbaum" folgt oder nicht

Zum Beispiel

wenn die Eingabe ist:

Ausgabe sollte falsch sein:

Da 4 im linken Teilbaum größer als der Wurzelwert ist (3)

Wenn die Eingabe ist:

Ausgabe sollte wahr sein

Algorithmus zum Überprüfen, ob ein bestimmter binärer Baum BST ist

Ein binärer Baum ist BST, wenn er eine der folgenden Bedingungen erfüllt:

1. Es ist leer
2. Es hat keine Unterbäume
3. Für jeden Knoten x im Baum müssen alle Schlüssel (falls vorhanden) im linken Teilbaum kleiner als Schlüssel (x) sein, und alle Schlüssel (falls vorhanden) im rechten Teilbaum müssen größer als Schlüssel (x) sein.

Ein einfacher rekursiver Algorithmus wäre also:

is_BST(root):
  if root == NULL:
   return true

  // Check values in left subtree
  if root->left != NULL:
    max_key_in_left = find_max_key(root->left)
    if max_key_in_left > root->key:
        return false

  // Check values in right subtree
  if root->right != NULL:
    min_key_in_right = find_min_key(root->right)
    if min_key_in_right < root->key:
        return false

  return is_BST(root->left) && is_BST(root->right)

Der obige rekursive Algorithmus ist korrekt, aber ineffizient, da er jeden Knoten mehrmals durchläuft.

Ein weiterer Ansatz zur Minimierung der mehrfachen Besuche jedes Knotens besteht darin, sich die minimalen und maximalen Werte der Schlüssel in der Teilstruktur zu merken, die wir besuchen. Der minimal mögliche Wert eines Schlüssels sei K_MIN und der maximale Wert K_MAX . Wenn wir von der Wurzel des Baums aus beginnen, ist der Wertebereich im Baum [K_MIN,K_MAX] . Der Schlüssel des Wurzelknotens sei x . Dann ist der Wertebereich im linken Teilbaum [K_MIN,x) und der Wertebereich im rechten Teilbaum ist (x,K_MAX] . Wir werden diese Idee verwenden, um einen effizienteren Algorithmus zu entwickeln.

is_BST(root, min, max):
    if root == NULL:
        return true

    // is the current node key out of range?
    if root->key < min || root->key > max:
        return false

    // check if left and right subtree is BST
    return is_BST(root->left,min,root->key-1) && is_BST(root->right,root->key+1,max)

Es wird zunächst aufgerufen als:

is_BST(my_tree_root,KEY_MIN,KEY_MAX)

Ein anderer Ansatz wird darin bestehen, den Binary-Baum in Ordnung zu durchlaufen. Wenn der Inorder-Durchlauf eine sortierte Folge von Schlüsseln erzeugt, ist der angegebene Baum eine BST. Um zu prüfen, ob die Reihenfolge sortiert ist, merken Sie sich den Wert des zuvor besuchten Knotens und vergleichen Sie ihn mit dem aktuellen Knoten.