檢查給定二叉樹是否為 BST 的演算法
如果二叉樹滿足以下任一條件,則為 BST:
- 它是空的
- 它沒有子樹
- 對於樹中的每個節點 x,左子樹中的所有鍵(如果有的話)必須小於鍵(x),並且右子樹中的所有鍵(如果有的話)必須大於鍵(x)。
所以一個簡單的遞迴演算法將是:
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)
上述遞迴演算法是正確但效率低的,因為它遍歷每個節點多次。
最小化每個節點的多次訪問的另一種方法是記住我們正在訪問的子樹中的鍵的最小和最大可能值。設任何鍵的最小可能值為 K_MIN
,最大值為 K_MAX
。當我們從樹的根開始時,樹中的值範圍是 [K_MIN,K_MAX]
。讓根節點的金鑰為 x
。那麼左子樹中的值範圍是 [K_MIN,x)
,右子樹中值的範圍是 (x,K_MAX]
。我們將使用這個想法來開發更有效的演算法。
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)
它最初將被稱為:
is_BST(my_tree_root,KEY_MIN,KEY_MAX)
另一種方法是按順序遍歷二叉樹。如果 inorder 遍歷產生一個已排序的鍵序列,則給定的樹是 BST。要檢查順序序列是否已排序,請記住先前訪問過的節點的值,並將其與當前節點進行比較。