從二叉樹到完全二叉樹

之是以會出現完全二叉樹的概念，是因為可由此在實體上，以線性表的方式實作邏輯上的完全二叉樹。

• 完全二叉樹的葉子節點隻能出現在最底部兩層；

1. 完全二叉樹

對于一棵高度為 h 的二叉樹，如果其第 0 層至 h−1 層（倒數第二層）都是滿的，也就是說，對所有 0≤i≤h−1 ，第 i 層有 2i 個結點，前 h−1 層的結點總數為 2h−1 。如果最下一層的結點不滿，則所有結點從最左邊開始連續排列。這樣的二叉樹就是一棵完全二叉樹。

2. 完全二叉樹的性質

我自己得到的一些結論如下：

• 從 0 開始編号，編号為奇數的必定在左子節點，編号為偶數的必定在右子節點；
• 對某一個内部結點（internal node）而言，不可能出現有右子節點，而沒有左子節點的情況；
• 完全二叉樹與線性結構有自然的雙向映射；
• n 個結點的完全二叉樹的葉節點的範圍是 n2∼n
  • 也即對完全二叉樹而言，（後）一半是葉節點，（前）一半是内部結點（包括根節點）

• n 個結點的完全二叉樹高度為 ⌊log2n⌋

  證，設完全二叉樹 T 包含 n 個結點，高度是 h 。則 n 與 h 的關系為：

  2h−1<n≤2h+1−1

  也即 2h≤n<2h+1 ，兩邊同時取對數得 h≤log2n<h+1 。可見 h 為不大于 log2n 的最大整數；

• （完全二叉樹）如果 n 個結點的完全二叉樹的結點按層次并按從左到右的順序從 0 開始編号，對任一節點 i（ 0≤i≤n−1 ）都有：
  • 序号為 0 的結點是根節點；
  • 對于 i>0 ，其父節點的編号為 i−12 ；
  • 對于 2×i+1<n ，其左子節點序号為 2×i+1 ，否則無左子節點；
  • 對于 2×i+2<n ，其左子節點序号為 2×i+2 ，否則無右子節點；
  證明如下，使用數學歸納法，
  • i⇒i−12 ⇒ i+1⇒i2
    • 證：當 i 為左節點時，i+1 為其父節點的右結點，也即 i+1 與 i 為同一父節點的兄弟節點，此時 i2 與 i−12 相等，因為要取整數
    • 當 i 為右結點時（i 為偶數）， 則 i+1 結點的父節點為 i−12+1 ，

  • i⇒2×i+1 ⇒ i+1⇒2×i+3

    同樣，分 i 為左節點和右節點，進行證明，

    • 左節點時，i+1 為其兄弟節點，顯然其左子節點為 2i+3
    • 右節點時，根據推算， i+1 （與 2i+1 、 2i+2 在同一層） 結點的左子節點為 2i+3
  • 完全二叉樹的一個重要特性，如上證明，它可以十分友善地存入一個表或數組，直接根據元素下标（index）就能找到下标對應結點的子節點或父節點，無須以其他方式記錄樹的結構資訊。
    • 如果第 i 層是滿的，也即第 i 層有 2i 個結點；根的下标是 0，第 i 層元素從 2i−1 的位置開始存放，連續 2i 個元素都屬于這一層；