algorithm
Kontrollera om ett träd är BST eller inte

Om ett givet ingångsträd följer egenskapen Binär sökträd eller inte

Till exempel

om ingången är:

Utmatningen ska vara falsk:

Eftersom 4 i det vänstra underträdet är större än rotvärdet (3)

Om ingången är:

Output bör vara sant

Algoritm för att kontrollera om ett givet binärt träd är BST

Ett binärt träd är BST om det uppfyller något av följande villkor:

1. Det är tomt
2. Den har inga underträd
3. För varje nod x i trädet måste alla nycklar (om någon) i det vänstra underträdet vara mindre än tangenten (x) och alla tangenterna (om några) i det högra underträdet måste vara större än tangenten (x).

Så en enkel rekursiv algoritm skulle vara:

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)

Ovanstående rekursiv algoritm är korrekt men ineffektiv, eftersom den korsar varje nod flera gånger.

Ett annat tillvägagångssätt för att minimera flera besök i varje nod är att komma ihåg minsta och max möjliga värden för tangenterna i undertråden vi besöker. Låt minsta möjliga värde för valfri nyckel vara K_MIN och maximivärde vara K_MAX . När vi börjar från trädets rot är värdena i trädet [K_MIN,K_MAX] . Låt nyckeln till rotnoden vara x . Sedan är värdet i vänster undertråd [K_MIN,x) och värdet i höger undertråd är (x,K_MAX] . Vi kommer att använda denna idé för att utveckla en effektivare algoritm.

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)

Det kommer ursprungligen att kallas som:

is_BST(my_tree_root,KEY_MIN,KEY_MAX)

Ett annat tillvägagångssätt kommer att vara att göra gränsöverskridande av binärträdet. Om inorder traversal producerar en sorterad sekvens av nycklar är det givna trädet en BST. För att kontrollera om ordningsföljden är sorterad, kom ihåg värdet på den tidigare besökta noden och jämför den med den aktuella noden.