tree - 堆什么时候变成完整的二叉树？

Question

我知道堆总是完整的二叉树。但我想知道什么时候堆是完整的二叉树？例如，堆必须处于什么条件才能始终是完整的二叉树？

Answer 1

为了说明为什么堆条件不重要，考虑很容易通过简单地为每个节点分配其高度来为满足堆条件的任何二叉树给出标记。（如果你想要唯一的标签，你可以对树进行拓扑排序并从根开始计数。）

因此，完整性和完整性也是堆的正交概念（在此处查看完整、完整、两者兼而有之树的示例）。

然而，堆实现通常选择以这样一种方式确保堆条件，即生成的二叉树是完整的。实现普通二叉堆的标准方法是使用一个数组，然后用隐式二叉堆从左到右填充它（这是堆排序通常实现的方式）。

如果这是您所指的那种堆，则约束会显着收紧，因为您总是从左到右一次填充一层。应该很明显为什么这样的树是完整的（除了最后一个之外的所有级别总是完全填充）。

还应该很容易看出它总是在 full 和 not full 之间交替：

• 如果它只有根，它是满的。
• 如果您将一个节点添加到一棵完整的树中，它的父节点必然只有一个（左）子节点，因此该树将不再是完整的。
• 如果您的树不再满了，下一次插入将使它再次满，因为它将作为您在上一步中给左孩子的父母的（右）孩子插入。