二分搜索树

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实际上是按照算法中描述的那样构建的。例如，在您的树中:节点'9‘不在正确的位置，因为当9< 10时，它应该在根节点'10’的左分支下。'14‘和'11’也是一样，它们应该在右边的分支上。

例如，BST可以是这样的：

    10
  5    11
3   8    12
          14

Answer 2

不要混淆二叉树和二进制搜索树。二叉树( BST)是一种特殊类型的二叉树，其中左边的所有节点都小于或等于父节点，右边的所有节点都大于父节点。

而你给出的例子只是一个二叉树，而不是一个二叉树。您可以看到，值11和14留给了父节点10，这违反了BST属性。看一下二进制搜索树的here。

Answer 3

你在不是BST中展示的树。11和14永远不会被插入到10的左边，这就是为什么算法不会在那里搜索。9也不合时宜。

根据维基百科插入：

当搜索开始时，

插入开始；如果根不等于值，我们像以前一样搜索左子树或右子树。最终，我们将到达一个外部节点，并将该值添加为其右或左子节点，具体取决于节点的值。换句话说，我们检查根，如果新值小于根，则将新节点递归插入到左子树中，如果新值大于或等于根，则向右子树递归插入新节点。

如果二叉树具有以下属性(也来自维基百科)，则可以断定它是BST：

1. 节点的左子树只包含关键字小于节点关键字的节点。
2. 节点的右子树只包含关键字大于节点关键字的节点。
3. 左子树和右子树也必须是二进制搜索树。