java - 字符串二分查找树

Question

我有一个关于字符串二叉搜索树到底如何工作的问题。我知道并且已经实现了整数的二叉搜索树，方法是检查新数据是否 <= 父数据，然后如果较小则向左分支，如果较大则向右分支。然而，我对如何使用字符串节点实现这一点有点困惑。

使用整数或字符，我可以将数组插入到我编程的树的插入方法中，并且它会正确构建树节点。我的问题是如何使用字符串数组来处理这个问题。如何让字符串在树中正确分支？例如，如果我有一系列问题，我如何才能正确地对 BST 进行分支，以便最终得到正确的答案。

例如，看看下面的简单树示例。

                                        land animal?            
                   have tentacles?------------^-------------indoor animal
          have claws?-----^----jellyfish    live in jungle?----^----does it bark?      
eat plankton?----^----lobster             bear----^----lion        cat----^----dog
shark----^----whale

您将如何填充这样的树，以便节点按照您想要的方式填充。我正在尝试制作 BST 来解决问题，但我很困惑如何填充字符串的节点，以便它们出现在正确的位置。您需要对节点进行硬编码吗？

Answer 1

更新 2，构建二元决策树:

二元决策树可以被认为是一堆问题，这些问题产生关于叶节点方面的 boolean 响应 - 方面要么存在/成立，要么不成立。也就是说，对于特定节点/边的每个后代，我们必须能够说“这个问题/答案成立”(答案可以是“真”或“假”)。例如，树皮是(正常)狗的一个侧面，但触手不是鲸鱼的一个侧面。在所呈现的树中，假边总是通向左子树:这是避免用 true/false 或 Y/N 标记每个边的约定。

这棵树只能根据现有/外部知识构建，允许人们回答每一种动物的每个问题。

这里是一个可以用来构建这样一棵树的粗略算法:

1. 从一组可能的动物开始，称之为 A，然后提出一组问题，称之为 Q。
2. 从 Q 中选择一个问题 q，其中 count(True(q, a in A)) 最接近 count(False(q, a in A)) - 如果生成的树是平衡二叉树，那么对于最佳问题来说，这些计数将始终相等。
3. 从Q中删除q并将其作为询问当前节点的问题。将所有 False(q,a) 放入左子节点可用的动物集合 (A') 中，将所有 True(q,a) 放入右子节点可用的动物集合 (A'') 中。
4. 按照每个边/分支(false=左，true=右)，从剩余的 Q 中选择一个合适的问题并重复(根据情况使用 A' 或 A'' 作为 A)。

(当然，在网上可以找到许多更完整/详细/准确的资源，如course material或whitepapers。更不用说在大多数大学校园都有合适的书籍选择了..)

<小时/>

更新，[二进制] decision tree :

在这种特殊情况下(通过添加的图表可以清楚地看出)，该图基于对问题的"is"或“否”回答，代表节点之间的边。也就是说，树不是使用字符串值本身的排序来构建的。在这种情况下，尽管如果允许非二进制响应，每个节点可以有更多的边/子节点，但始终让左分支“假”和右分支“真”可能是有意义的。

决策树必须是 "trained" (google search) 。也就是说，图必须首先基于问题/响应来构建，这与仅基于节点之间的排序的 BST 不同。最初的图形构建不能仅仅通过一系列问题来完成，因为边不遵循内在的顺序。

<小时/>

初始响应，针对 binary search tree :

与整数的处理方式相同:算法不会改变。

考虑一个函数，compareTo(a,b)，对于 a < b、a == b 和 a > b 分别返回 -1、0 或 1。

然后，如果 a 和 b 的类型支持排序，那么在使用此合约实现函数时，考虑到 a 和 b 的类型都无关紧要(只要它们相同):对于整数来说它将是“原始”，对于字符串类型将使用宿主语言相应的字符串比较。