二叉搜索树

Question

这是维基百科上关于二叉搜索树的一些代码：

```c++ struct node { int key_value; node *left; node *right; };

class btree { public: btree(); ~btree();

void insert(int key); node *search(int key); void destroy_tree(); private: void destroy_tree(node *leaf); void insert(int key, node *leaf); node *search(int key, node *leaf);

node *root; }; ```

以上是二叉搜索树的结构体和类定义，其中包括插入、查找和销毁二叉树等操作。

# '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确实存在于我的树中，只不过在另一侧。

请问此算法在我的树上能够工作的二叉树有哪些限制？

谢谢。

- Martin

Answer 1

这是因为你的树不是一棵二叉搜索树：它的排序方式不正确。实际上，BST是按照算法描述来构建的。例如在你的树中，节点“9”的位置不正确，因为由于 9 < 10，它应该在根节点“10”的左分支下方。同样的，'14'和 '11'也应该在右分支上。

例如，BST可以像这样：

    10
  5    11
3   8    12
          14

- pierroz

---

非常感谢PerrOz。这解释了我对BSTs的部分困惑 :) - Martin

Answer 2

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

而你提供的例子只是一个普通的二叉树，而不是二叉搜索树。你可以看到值为11和14的节点位于父节点10的左侧，违反了BST的属性。请查看二叉搜索树这里。

- bragboy

---

你如何称呼父节点？如果左侧的所有节点都小于或等于祖先，但不是父节点右侧，则这是有意义的吗？另外，我的意思是4而不是14。我已经修复了树。 - Martin

请参考以下链接了解所有术语。http://www.technicalypto.com/2010/01/binary-trees-in-java.html - bragboy

Answer 3

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

根据维基百科的插入方法：

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

您可以通过以下属性告诉二叉树是否为二叉搜索树（也来自维基百科）：

1.节点的左子树仅包含键小于节点键的节点。 2.节点的右子树仅包含键大于节点键的节点。 3.左子树和右子树都必须是二叉搜索树。

- Amir Rachum

Answer 4

您将节点14和11放错了位置。请参考二叉搜索树的维基百科文章：

• 一个节点的左子树只包含键值小于该节点的键值。
• 一个节点的右子树只包含键值大于该节点的键值。
• 左右子树都必须是二叉搜索树。

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

- Jesse Dhillon

Answer 5

你的树不是二叉搜索树

- Hiber