二叉搜索树

这是关于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

现在，这里的二叉树：

如果我在寻找11，我按照算法那里，我从10开始，我右转到12，然后从左到9，然后到达树的尽头，但没有发现11. 但是11存在于我的树中，它只存在于另一侧。

你能解释一下二叉树中这个算法在我的树上工作的限制吗？

谢谢。

来源

2010-09-07 Martin

这只是因为你的树不是二叉搜索树：没有正确排序。 BST按照算法中的描述进行构建。例如在你的树中：节点'9'不在正确的位置，因为它应该在你的根节点'10'的左边。 '14'和'11'应该在右侧分支上。

例如一个BST可能某事像这样：

来源

2010-09-07 05:37:39 PierrOz

非常感谢PerrOz。这解释了我没有得到关于BST的部分:) – Martin 2010-09-07 05:44:18

不要在二叉树和二叉搜索树之间混淆。二叉搜索树（简称BST）是一种特殊类型的二叉树，其中左侧的所有节点都小于或等于父节点，所有节点的右侧都大于父节点。

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

来源

2010-09-07 05:34:26 bragboy

你叫什么父节点？如果左边的所有节点都小于或等于祖先，而不是父权，那么这会有意义吗？我的意思是4而不是14。我固定了树。 – Martin 2010-09-07 05:37:04

请参阅此链接了解所有的行话。 http://www.technicalypto.com/2010/01/binary-trees-in-java.html – bragboy 2010-09-07 05:38:21

您已将节点14和11放在错误的地方。从the Wikipedia article on BSTs：

节点的左子树只包含键小于节点的关键节点。

节点的右子树只包含密钥大于节点密钥的节点。

左右子树也必须是二叉搜索树。

正如你所看到的，14和11是大于8

来源

2010-09-07 05:35:16

14,11和9是错误的。 – 2010-09-07 05:37:46

你不是一个BST呈现的树。 11和14从未插入到10的左侧，这就是为什么算法不在那里搜索。 9也不合适。根据维基百科

插入：

插入开始作为搜索将开始;如果根不等于这个值，我们像以前一样搜索左边或右边的子树。最终，我们将到达一个外部节点，并根据节点的值将值添加为其右侧或左侧的子节点。换句话说，我们检查根，如果新值小于根，则递归插入新节点到左侧子树，如果新值大于或等于根，则递归插入新子节点。

你可以告诉大家一个二叉树是BST，如果它具有这些属性（也来自维基百科）：

节点的左子树只包含键节点小于节点键。

节点的右侧子树只包含密钥大于节点密钥的节点。

左右子树也必须是二叉搜索树。

来源

2010-09-07 05:35:22

你的树不是二叉搜索树

来源

2010-09-07 05:58:51 Hiber

回答

相关问题