堆什麼時候變成完整的二叉樹？

Question

我知道堆總是完整的二叉樹。但我想知道什麼時候堆滿了二叉樹？比如堆必須滿足什麼條件才能成爲完整的二叉樹？

Answer 1

爲了說明爲什麼堆狀況不重要，考慮通過簡單地爲每個節點分配其高度，很容易給出一個標記來滿足堆狀況的任何二叉樹。 （如果你想要獨特的標籤，你可以對樹進行拓撲排序並從根開始計數。）

因此完整性和豐滿度也是堆的正交概念（查看here瞭解完整，完整，兩者都不）。

但是，通常堆實現選擇確保堆條件的方式使得生成的二叉樹是完整的。一個實現普通二進制堆的標準方法是使用一個數組，然後用一個隱式二進制堆從左到右填充它（這是通常實現堆排序的方式）。

如果這是你指的那種堆，那麼約束會顯着收緊，因爲你總是從左到右一次填充樹。這應該是顯而易見的，爲什麼這樣的樹是完整的（所有級別，但最後一個總是完全填充）。

也應該很容易看出，它總是滿滿的，不完全之間交替：

• 如果它只有根部，它充滿。
• 如果您將節點添加到完整樹中，則其父節點必須只有一個（左）子節點，因此該樹將不再滿。
• 如果你的樹不再滿了，下一次插入會再次填滿它，因爲它將作爲你在上一步中給出左孩子的父母的（右）孩子插入。