这是关于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存在于我的树中,它只存在于另一侧。
你能解释一下二叉树中这个算法在我的树上工作的限制吗?
谢谢。
非常感谢PerrOz。这解释了我没有得到关于BST的部分:) – Martin 2010-09-07 05:44:18