二叉搜索树

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