5

这是在维基百科上找到的关于 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 存在于我的树中，它只是在另一边。

您能否解释一下二叉树中该算法​​在我的树上工作的限制是什么？

谢谢。

4

5 回答 5

10

这只是因为您的树不是二叉搜索树：它的排序不正确。BST 实际上是按照算法中的描述构建的。例如在你的树中：节点'9'不在正确的位置，因为 9 < 10 它应该在你的根节点'10'的左分支下。'14' 和 '11' 相同，它们应该在正确的分支上。

例如，BST 可能是这样的：

    10
  5    11
3   8    12
          14
于 2010-09-07T05:37:39.173 回答
3

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

而您给出的示例只是二叉树而不是二叉搜索树。您可以看到值 11 和 14 留给了父节点 10，这违反了 BST 属性。看看这里的二叉搜索树。

于 2010-09-07T05:34:26.307 回答
3

您在不是 BST 中呈现的树。11 和 14 永远不会插入到 10 的左侧，这就是算法不在那里搜索的原因。9也是不合适的。

根据维基百科插入：

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

如果二叉树具有以下属性（也来自维基百科），您可以判断它是 BST：

  1. 节点的左子树仅包含键小于节点键的节点。
  2. 节点的右子树只包含键大于节点键的节点。
  3. 左右子树也必须是二叉搜索树。
于 2010-09-07T05:35:22.657 回答
1

您将节点 14 和 11 放置在错误的位置。来自关于 BST 的 Wikipedia 文章：

  • 节点的左子树仅包含键小于节点键的节点。
  • 节点的右子树只包含键大于节点键的节点。
  • 左右子树也必须是二叉搜索树。

如您所见，14 和 11 都大于 8。

于 2010-09-07T05:35:16.510 回答
1

你的树不是二叉搜索树

于 2010-09-07T05:58:51.073 回答