检查给定二叉树是否为 BST 的算法

如果二叉树满足以下任一条件，则为 BST：

1. 它是空的
2. 它没有子树
3. 对于树中的每个节点 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。要检查顺序序列是否已排序，请记住先前访问过的节点的值，并将其与当前节点进行比较。