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

Question

我知道堆总是完整的二叉树。但我想知道什么时候堆满了二叉树？比如堆必须满足什么条件才能成为完整的二叉树？

Answer 1

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

因此完整性和丰满度也是堆的正交概念（查看here了解完整，完整，两者都不）。

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

如果这是你指的那种堆，那么约束会显着收紧，因为你总是从左到右一次填充树。这应该是显而易见的，为什么这样的树是完整的（所有级别，但最后一个总是完全填充）。

也应该很容易看出，它总是满满的，不完全之间交替：

• 如果它只有根部，它充满。
• 如果您将节点添加到完整树中，则其父节点必须只有一个（左）子节点，因此该树将不再满。
• 如果你的树不再满了，下一次插入会再次填满它，因为它将作为你在上一步中给出左孩子的父母的（右）孩子插入。