目錄
重要的術語澄清
完美二叉樹 (Perfect Binary Tree)
完全二叉樹 (Complete Binary Tree)
大比拼 (Comparison)
相互關系的第一性推導?
我們來深入探討兩種在算法中非常重要的、具有特定“形狀”的二叉樹：滿二叉樹 (Full Binary Tree) 和 完全二叉樹 (Complete Binary Tree)。
最關鍵的是，我們會將它們與之前學過的嚴格二叉樹 (Strict Binary Tree) 進行詳細的比較。
數據結構：嚴格二叉樹 (Strict Binary Tree)-CSDN博客
這三者之間的區別和聯系是常考點，也是一個非常容易混淆的地方，所以這次的第一性推導會特別注重辨析。
重要的術語澄清
在開始之前，我必須先解決一個長期困擾學習者的問題：術語混亂。
-
Strict Binary Tree (嚴格二叉樹): 我們已經學過，定義非常清晰——每個節點要么有0個孩子，要么有2個孩子。
-
Full Binary Tree: 這是最混亂的術語。
-
在很多國際經典教材（如《算法導論》）和學術界中，"Full Binary Tree" 就是我們學的 "Strict Binary Tree"。
-
但是，在中國國內的很多教材中，“滿二叉樹” 指的是一種結構最完美的樹，即所有葉子都在同一層。為了避免這種語義混淆，我們把這種最完美的樹稱為 完美二叉樹 (Perfect Binary Tree)。
-
-
Complete Binary Tree (完全二叉樹): 這個術語的定義是統一的，沒有爭議。
為了本次學習的清晰性，我們將采用以下定義:
-
嚴格二叉樹 (Strict Binary Tree): 度為0或2。
-
完美二叉樹 (Perfect Binary Tree): 國內教材中的“滿二叉樹”，是一種極致形態。
-
完全二叉樹 (Complete Binary Tree): 為數組表示法而生的結構。
完美二叉樹 (Perfect Binary Tree)
讓我們從一個問題開始——一棵二叉樹最“完美”、最“飽滿”、最“對稱”的形態應該是什么樣的？
推導1 ——飽滿：要想“飽滿”，內部就不應該有任何浪費的空間。
任何一個非葉子節點，如果只掛了一個孩子，那它的另一個孩子位就空著，這不“飽滿”。
所以，所有非葉子節點都必須有兩個孩子。（這恰好是嚴格二叉樹的定義）。
推導2 ——對稱：?要想“對稱”，樹的末端應該是整齊劃一的。
如果有些葉子在第3層，有些在第4層，那這棵樹看起來就像參差不齊的灌木，不夠“完美”。
所以，所有的葉子節點必須在同一層。
h = 2 (高度 2)●/ \● ●/ \ / \● ● ● ●
將這兩個推論合二為一，就得到了完美二叉樹 (Perfect Binary Tree) 的定義：
一棵深度為 k 且有 2^(k + 1) ? 1 個節點的二叉樹。用更直觀的語言描述就是：
-
它是一棵嚴格二叉樹。
-
并且，它所有的葉子節點都在最下面一層。
這棵樹的形狀像一個完美的等腰三角形，沒有任何空缺。
性質:
-
節點數與高度的關系是固定的：對于高度為
h的完美二叉樹，其節點數n永遠是它能達到的最大值，不多不少，即 n = 2^(h + 1) ? 1。 -
它是嚴格二叉樹的一種非常特殊的特例。
完全二叉樹 (Complete Binary Tree)
完美二叉樹的要求太苛刻了。如果我有6個節點，就無法構成一棵完美二叉樹（高度為1的完美樹有3個節點，高度為2的有7個）。
那么，在節點數不“完美”的情況下，如何讓樹的形態盡可能地緊湊、不浪費空間呢？
推導1 ——填充順序：?要想緊湊，我們應該從上到下，一層一層地去填充節點。不能第2層還沒滿，就去放第3層的節點。
所以，樹的所有層，除了最后一層，都必須是滿的（即構成一個完美二叉樹）。
推導2 ——最后一層的排列：?對于最后一層，節點可能沒有填滿。那這些節點應該怎么放？是隨便放，還是靠右放，還是靠左放？
為了“緊湊”，最自然的方式就是從左到右依次排列，中間不能有空隙。
滿二叉樹 (高度 2):●/ \● ●/ \ / \● ● ● ●完全二叉樹（去掉最右葉子）:●/ \● ●/ \ / ● ● ●
將這兩個推論合二為一，就得到了完全二叉樹 (Complete Binary Tree) 的定義：
一棵二叉樹，如果它除了最底層之外的其他各層都被完全填滿，并且最底層的所有節點都連續地集中在左邊，那么它就是一棵完全二叉樹。
這個“從上到下，從左到右，連續排列”的特性，使其與數組表示法完美契合！
數據結構：二叉樹的表示方式（Representation of Binary Trees）-CSDN博客
當你按層序遍歷一個完全二叉樹時，得到的節點序列可以不多不少、不留一個空位地（沒有-1作為占位符）存入一個數組中。
完全二叉樹這個概念，可以說就是為了高效的數組表示法而生的。 這是理解它的關鍵。
大比拼 (Comparison)
現在我們把三個概念放在一起，從不同維度進行比較。
| 對比維度 | 嚴格二叉樹 (Strict) | 完美二叉樹 (Perfect) | 完全二叉樹 (Complete) |
|---|---|---|---|
| 一句話定義 | 節點度數要么是0，要么是2 | 節點全滿，葉子在同一層 | 節點按層序連續排列 |
| 允許的節點度 | 只有 0 和 2 | 只有 0 和 2 | 可以是 0, 1, 2<br>(最多只允許有一個度為1的節點) |
| 形狀要求 | 無特定形狀要求，可高可矮 | 必須是完美的金字塔形 | 必須是“左對齊”的緊湊形狀 |
| 和別人的關系 | 是一個比較寬泛的分類 | 是嚴格二叉樹的特例<br>是完全二叉樹的特例 | 不一定是嚴格二叉樹<br>(當節點總數為偶數時，必有1個度為1的節點) |
| 數組表示法 | 如果很“瘦”，會浪費巨大空間 | 空間利用率100%，沒有浪費 | 空間利用率100%，完美適配 |
相互關系的第一性推導?
我們可以把這些樹的集合想象成幾個圈：
1. 完美二叉樹是標準最嚴苛的。它既要求所有內部節點度為2（滿足嚴格定義），又要求節點是連續的（滿足完全定義）。
所以，完美二叉樹的圈是最小的，它同時位于嚴格樹和完全樹兩個圈的交集之內。
-
完美 => 嚴格(成立) -
完美 => 完全(成立)
完美二叉樹： ●/ \● ●/ \ / \● ● ● ●/ \ / \ / \ / \● ● ● ● ● ● ● ●
2. 嚴格二叉樹只對節點的“度”有要求。它不關心節點是不是“左對齊”。你可以構造一棵嚴格二叉樹，它中間有空位，因此它不是完全二叉樹。
-
嚴格 => 完全(不成立)
嚴格二叉樹：●/ \● ●/ \● ●/ \ / \● ● ● ●
3. 完全二叉樹只對節點的“位置”有要求。它不關心節點的“度”。當節點總數是偶數時，必然會產生一個只有一個左孩子的節點，它的度是1，這就不滿足嚴格二叉樹的定義。
-
完全 => 嚴格(不成立)
完全二叉樹：●/ \● ●/ \ / \● ● ● ●/ \ / ● ● ●
結論:
-
完美二叉樹 是最特殊、最規整的，它同時是一棵嚴格二叉樹和一棵完全二叉樹。
-
嚴格二叉樹 和 完全二叉樹 是從兩個不同維度（“度” vs “位置”）對樹進行的約束，它們有交集（交集就是完美二叉樹），但誰也不是誰的子集。
理解了這些從基本原則出發的定義和它們之間的邏輯關系，你就再也不會把這幾個概念搞混了。
