接續昨天的樹。二元樹 (Binary Tree) 的特點就是每個節點最多有兩個兒子，或者是說每個節點最多有兩棵子樹。

二元樹中還有兩種特殊的種類：

• 滿二元樹
• 完全二元樹

滿二元樹

若二元樹中的每個節點都有兩個兒子(子節點)，就稱滿二元樹。或者說滿二元樹的所有葉節點都有同樣的深度。較嚴格的定義為 一棵深度為 h 且有 個節點的二元樹 。

完全二元樹

若二元樹的高度(深度)為 h，除第 h 層外，其他各層(1 ~ h-1)的節點數都達到最大個樹，而第 h 層從右向左連續缺幾個節點，則這個二元樹就稱 完全二元樹。



其實完全二元樹很類似這樣的形狀。

在瞭解了完全二元樹的定義之後，那要怎麼把完全二元樹的資料儲存起來？答案是一個一維陣列就可以搞定。

首先將完全二元樹進行編號，從上到下，從左到右。

[1, 2, 3, 4, 5, 6]

如果仔細觀察就可以發現編號和一維陣列儲存的規律。

• 父節點編號為 k
• 左兒子的編號為 2＊k
• 右兒子的編號為 2＊k+1
• 如果兒子編號為 x ，父節點的編號就為 x/2 取整數的商。
• 如果有 N 個節點，則完全二元樹的高度(深度)為