我有一本书以一种非常糟糕的方式解释了二叉搜索树背后的理论我知道左右孩子的顺序都有一些东西，但我仍然无法理解一个大于另一个前一个级别的想法。
以这个字符串树为例：
（对不起我的油漆）这个例子直接取自我的书:)
有人可以向我解释订单吗？这背后的逻辑是什么？
问问题
39569 次
5 回答
9
在 BST 中，每个节点最多有一个左孩子和一个右孩子。给定节点左侧的每个节点都小于它，而给定节点右侧的每个节点都大于它。这样做的后果之一是你不能有重复的值，所以我不确定这个例子是否正是这本书的内容。
在您的示例中，字符串按字母顺序排列。以根节点为例，Bob 在 Karen 之前，所以 Bob 在 Karen 的左边。汤姆在凯伦之后，所以汤姆在凯伦的右边。从整个树来看，您可以看到 Karen 左侧的每个节点（Bob、Alan、Ellen）按字母顺序排在 Karen 之前，而 Karen 右侧的每个节点（Tom、Wendy）按字母顺序排在 Karen 之后。无论您查看哪个节点，此模式都是相同的。
于 2012-12-26T16:01:03.627 回答
2
对于任何节点（例如，Karen - 根），左子树中的每个节点（Bob、Alan、Ellen）在字典上都小于 Karen，而右子树中的每个节点（Tom、Wendy）都大于 Karen。
正如@mellamokb 在评论中指出的那样，第二个凯伦不应该在那里。
因此，您可以在 O(log N) 时间内对这棵树进行二分搜索，就像搜索排序数组一样。
于 2012-12-26T16:01:27.497 回答
0
对于任何节点：
- 左分支中的所有内容都按字母顺序排列<当前节点。
- 右分支中的所有内容都按字母顺序排列 > 当前节点。
这提供了几个独特的属性
- 您可以通过简单地根据您要搜索的键在字典上是 < 还是 > 而不是当前节点来找到任何节点。您将及时到达目的地或不匹配的叶节点（在这种情况下，密钥不存在）
O(Log n)。 - 有序遍历按字母顺序给出所有键。
于 2012-12-26T16:02:05.553 回答
0
在您的示例中，它们表示每个名称中第一个符号的顺序。
如果您看到，名称顺序从左到右是从 ABC 中的第一个字符到最后一个字符。
此外，Karen 名称的第二次出现有一个特殊情况 - 如果输入相同的数据，此树中的默认行为是“向右移动”，那么 Karen 与 Tom 相比 -> K 是“更小”的 T，所以它离开它。
无论如何，这是一个更好的例子，从中您可以看到二叉树中的订单号：http: //www.codeproject.com/Articles/4647/A-simple-binary-tree-implementation-with-VB-NET
于 2012-12-26T16:04:23.523 回答
-1
我认为下面的这篇文章对你理解二叉树的概念很有帮助，它还提供了 C/C++ 和 Java 中的常见代码示例：
于 2012-12-26T16:12:05.820 回答