c# - 构造二叉树图

Question

这是一个二叉树图。我无法理解图表是如何创建的。你有 5 在顶部，但你如何决定接下来的数字和顺序？有人可以逐步指导我吗？

Answer 1

听起来您对该链接上的图表感到特别困惑。该图似乎有错误。

正如其他人所说，有多种有效的安排，但对排序二叉树的要求是每个节点的左子树只包含较小的元素，而右子树只包含较大的元素。

在您的问题中提供的链接的图表中，由于 6 > 5，这违反了。元素 6 属于 5 的右子树，这似乎是作者的一个简单错误。

Answer 2

当然，

好吧，你说这是二叉树。所以算法是这样的：插入新数字时，如果数字较小，则向左，如果较大，则向右。您应该检查此小程序以生成二叉树以了解其工作原理

小程序链接

Answer 3

数字的特定排列不是规范的（即存在其他有效排列）。唯一的要求是每个节点的左子树只包含较小的节点，而右子树只包含较大的节点。

实现特定排列的方式取决于用于填充它的算法以及插入值的顺序。这在“平衡树”部分的文章中进行了部分解释。插入时，您需要保持树平衡。重新平衡的频率以及如何重新平衡是数百万页教科书、研究论文和代码行的主题。

简而言之，您的问题的答案是“视情况而定”。

对于不一定产生平衡树的朴素实现，每个插入只是简单地遍历树，如果数字小于当前访问的节点，则向左，或者如果它更大，则向右（忽略相等的值，您需要要么确保不会发生，要么决定处理它们的政策）。当您到达死胡同（即空左或右指针）时，用插入的值在那里插入一个新节点。

边栏：值得注意的是，朴素算法在极少数情况下可以满足您的需求，这要归功于其简单性。您可以通过在插入之前随机打乱输入数据来避免不平衡的树。然而，在大多数情况下，最好不要使用二叉树。哈希表几乎总是更可取的。