binary-tree - 带字符串的二叉搜索树

Question

我有一本书以一种非常糟糕的方式解释了二叉搜索树背后的理论级别。

以这个字符串树为例:

(对不起我的油漆)这个例子直接取 self 的书:)

有人可以向我解释一下顺序吗？这背后的逻辑是什么？

Answer 1

在 BST 中，每个节点最多有一个左 child 和一个右 child 。给定节点左侧的每个节点都小于它，而给定节点右侧的每个节点都大于它。这样做的后果之一是你不能有重复的值，所以我不确定这个例子是否正是这本书的内容。

在您的示例中，字符串按字母顺序排列。以根节点为例，Bob 在 Karen 之前，所以 Bob 在 Karen 的左边。汤姆在凯伦之后，所以汤姆在凯伦的右边。从整个树看，您可以看到 Karen 左侧的每个节点(Bob、Alan、Ellen)按字母顺序排在 Karen 之前，而 Karen 右侧的每个节点(Tom、Wendy)按字母顺序排在 Karen 之后。无论你看哪个节点，这个模式都是一样的。