二叉搜索树

Question

这是在维基百科上找到的一些关于二叉搜索树（BST）的代码：

# 'node' refers to the parent-node in this case
 def search_binary_tree(node, key):
     if node is None:
         return None  # key not found
     if key < node.key:
         return search_binary_tree(node.leftChild, key)
     elif key > node.key:
         return search_binary_tree(node.rightChild, key)
     else:  # key is equal to node key
         return node.value  # found key

现在来看一个二叉树：

       10
    5        12
  3   8    9   14
     4 11  

假设我在找数字11，如果按照上面的算法，我从10开始，先往右走到12，然后再往左走到9。结果我在树的末端没有找到11。

其实11在我的树里，只是它在另一边。

能不能请你解释一下，二叉树在什么情况下，这个算法才能在我的树上正常工作呢？

谢谢。

Answer 1

不要把二叉树和二叉搜索树搞混。二叉搜索树（简称BST）是一种特殊的二叉树，里面的规则是：左边的节点值都小于或等于父节点的值，而右边的节点值都大于父节点的值。

而你给出的例子只是一个普通的二叉树，并不是二叉搜索树。你可以看到，值为11和14的节点在父节点10的左边，这就违反了二叉搜索树的规则。想了解更多关于二叉搜索树的内容，可以看看这里。

Answer 2

你展示的这个树不是一个二叉搜索树（BST）。11和14不可能被放在10的左边，这就是为什么算法不去那边查找的原因。9的位置也不对。

根据维基百科，插入的过程是这样的：

插入的过程开始时就像查找一样；如果根节点的值和要插入的值不相等，我们就会像之前那样去查找左子树或右子树。最终，我们会找到一个空节点，然后根据这个节点的值，把新值作为它的左孩子或右孩子插入。换句话说，我们先看根节点，如果新值小于根节点，就递归地插入到左子树；如果新值大于或等于根节点，就插入到右子树。

你可以通过以下几个特征来判断一个二叉树是否是二叉搜索树（BST），这些也是来自维基百科的内容：

1. 一个节点的左子树只包含比这个节点的值小的节点。
2. 一个节点的右子树只包含比这个节点的值大的节点。
3. 左子树和右子树本身也必须是二叉搜索树。

Answer 3

这只是因为你的树不是一个二叉搜索树：它的顺序不对。二叉搜索树的构建是按照算法描述的方式进行的。举个例子，在你的树中：节点'9'的位置不对，因为9小于10，所以它应该在根节点'10'的左边。同样，'14'和'11'也应该在右边。

比如，一个二叉搜索树可以是这样的：

    10
  5    11
3   8    12
          14