1

我有一个关于字符串二叉搜索树究竟是如何工作的问题。我知道并且已经通过检查新数据是否<=父数据然后通过左分支（如果它更小或右分支如果它更大）来实现整数的二进制搜索树。但是，我对如何用字符串节点实现这一点有点困惑。

使用整数或字符，我可以将数组插入到我编程的树的插入方法中，并正确构建树节点。我的问题是如何使用字符串数组进行处理。你如何让琴弦在树上正确分支？例如，如果我有一系列问题，我将如何正确地对 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，但我很困惑如何填充字符串的节点，以便它们出现在正确的位置。您需要对节点进行硬编码吗？

4

1 回答 1

1

更新 2，构建二叉决策树：

可以将二叉决策树视为一堆问题，这些问题会产生关于叶节点方面的布尔响应 - 方面要么存在/保持真实，要么不存在。也就是说，对于特定节点/边的每个后代，我们必须能够说“这个问题/答案成立”（答案可以是“真”或“假”）。例如，树皮是（正常）狗的一个侧面，但触须不是鲸鱼的一个侧面。在呈现的树中，假边总是通向左子树：这是避免用真/假或 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. 在每个边缘/分支（假=左，真=右）之后，从剩余的 Q 中选择一个合适的问题并重复（根据需要使用 A' 或 A'' 代表 A）。

（当然，网上有很多更完整/详细/准确的资源作为课程材料或白皮书。更不用说大多数大学校园里合适的书籍选择了..）

更新，对于 [binary]决策树：

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

决策树必须经过“训练”（谷歌搜索）。也就是说，必须首先基于问题/响应来构建图，这与仅基于节点之间排序的 BST 不同。最初的图构建不能仅仅从一系列问题中完成，因为边不遵循内在的顺序。

初始响应，对于二叉搜索树：

与整数相同的方式：算法不会改变。

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

然后考虑 a 和 b 的类型都无关紧要（只要它们相同），如果这种类型支持排序，则在使用此合约实现函数时：它将是整数的“原始”并使用宿主语言的相应字符串比较对于字符串类型。

于 2013-03-17T18:52:16.370 回答