想像你正在闖一座迷宮：每到一個路口，最多只能選左邊或右邊。有些路口兩條路都通，有些只開一邊，走到盡頭就沒有下一個路口。把路口當成節點、路線當成連結，這種每個節點最多分出左右兩個位置的結構，就是二元樹（binary tree）。而且左、右位置各有固定意義，不能把它們當成沒有區別的兩條分支。

二元樹的定義

二元樹可以是空樹，也可以由一個根節點，以及它的左子樹和右子樹組成；左右子樹本身也各是一棵二元樹。換句話說，每個節點都只有「左」和「右」兩個可能的位置，不會有第三個子節點。

例如：

      A
     / \
    B   C
     \
      D

B 只有右子節點 D，左子節點的位置是空的。左右位置不能因為其中一邊空著就互相挪動；這也是二元樹和「每個節點最多有兩個子節點，但子節點沒有左右次序」的差別。

二元樹只規定節點的位置關係，不代表資料已經由小到大排列。

二元樹的基本運算

把二元樹當成一種資料結構時，常見的基本運算包括：

前序、中序、後序等走訪順序會影響節點被處理的次序，但不會改變樹本身的連結方式。這些走訪方式和背後用到的遞迴，之後會再詳細說明。

傾斜樹：形狀像一條鏈

如果每個非葉節點都只有一個子節點，而且節點一路偏向同一側，樹的形狀就像一條斜線，稱為傾斜樹（skewed tree）。子節點都在左側的是左斜樹，都在右側的是右斜樹。

左斜樹                    右斜樹
      A                        A
     /                          \
    B                            B
   /                              \
  C                                C
 /                                  \
D                                    D

雖然它仍然是二元樹，但每個節點幾乎都得沿著唯一的子節點往下找，形狀不像左右分散的樹。

完美與完整二元樹

「每個節點最多兩個子節點」之外，還可以再用其他條件描述二元樹的形狀：

完美二元樹的一個例子如下，每一層都填滿，所有葉節點都在最底層：

        A
       / \
      B   C
     / \ / \
    D  E F  G

完整二元樹則允許最底層沒有填滿，但節點必須靠左排列：

        A
       / \
      B   C
     / \ /
    D  E F

這棵完整二元樹的最底層少了 C 的右子節點；因為空位都在最右邊，所以仍符合完整二元樹的條件。反過來，如果最底層只有 D、E 和 C 的右子節點，C 的左子節點位置卻空著，中間就出現空位，不算完整二元樹。

完美二元樹一定是完整二元樹，因為它連最底層都填滿了；但完整二元樹的最底層可以不滿，所以不一定是完美二元樹。

二元樹的特性

沿用 Day 13 從根節點第 1 層開始計算的方式，樹的高度是最大層次。每往下一層，每個節點最多分出兩個子節點，所以每層最多的節點數會翻倍：

                  A               第 1 層：1 個
                /   \
              B       C           第 2 層：2 個
             / \     / \
            D   E   F   G         第 3 層：4 個

圖中每一層都剛好達到最多節點數，三層加起來共 1 + 2 + 4 = 7 個節點，所以這是高度 3 的完美二元樹。A、B、C 都有兩個子節點；D、E、F、G 是葉節點，4 = 3 + 1，也能看出葉節點比有兩個子節點的節點多 1 個。

由此可以得到三個常用特性：

1. 第 i 層最多有 2^(i−1) 個節點。
2. 高度為 h 的非空二元樹最多有 2^h − 1 個節點。 把每層的最大值加起來：1 + 2 + 4 + … + 2^(h−1) = 2^h − 1。剛好達到這個數量的，就是完美二元樹。
3. 非空二元樹的葉節點數比「有兩個子節點的節點數」多 1。 若 n₀ 表示葉節點數、n₂ 表示有兩個子節點的節點數，則 n₀ = n₂ + 1。

第 3 點可以這樣理解：設一棵非空二元樹中，n₁ 是只有一個子節點的節點數，全部節點數 n = n₀ + n₁ + n₂。除了根節點，每個節點都有一條連到父節點的線，所以共有 n − 1 條線；另一方面，這些線都是從父節點分出來的，數量是 n₁ + 2n₂。兩邊相等：

n₀ + n₁ + n₂ − 1 = n₁ + 2n₂
             n₀ = n₂ + 1

用前面的例子驗證：完美二元樹有 D、E、F、G 四個葉節點，A、B、C 三個節點有兩個子節點，4 = 3 + 1；完整二元樹有 D、E、F 三個葉節點，只有 A、B 有兩個子節點，3 = 2 + 1。

用陣列建立二元樹

二元樹可以存進一維陣列。做法是把樹想像成一棵完美二元樹，由上而下、由左而右替每個位置編號，再把節點放進對應的索引。為了讓公式簡單，這裡從索引 1 開始使用，索引 0 空著不用。

編號之後，節點之間的位置關係可以直接算出來：

以前面的完整二元樹為例：

索引：  1   2   3   4   5   6
資料：  A   B   C   D   E   F

B 在索引 2，左子節點在 2 × 2 = 4，也就是 D；右子節點在 2 × 2 + 1 = 5，也就是 E。F 在索引 6，父節點在 6 / 2 = 3，也就是 C。因為完整二元樹的節點靠左連續排列，實際存放節點的索引範圍不會有空位；若陣列容量大於節點數，尾端仍可能有未使用的位置。

但右斜樹就不同了。A、B、C、D 一路都是右子節點，索引會是 1、3、7、15：

索引：  1   2   3   4   5   6   7   8  ...  15
資料：  A   -   B   -   -   -   C   -  ...   D

只有 4 個節點，卻要準備 15 個位置，其中 11 個是空的。所以陣列表示法適合完整二元樹；樹形越不平均，浪費的空間越多。

用鏈結建立二元樹

另一種方式是讓每個節點各自存在，再用指標連起來，就像 Day 7 的鏈結串列。二元樹的節點需要三個欄位：

以開頭那棵 A、B、C、D 的樹為例，用鏈結表示會是這樣：

建立這棵樹的過程可以拆成幾個步驟：

1. 配置節點 A，把 left、right 先設為 NULL，再讓 root 指向 A。
2. 配置節點 B，讓 A 的 left 指向 B。
3. 配置節點 C，讓 A 的 right 指向 C。
4. 配置節點 D，讓 B 的 right 指向 D。B 的 left 保持 NULL，表示左子節點的位置是空的。

每個新節點一開始的左右欄位都是 NULL，等到有子節點要接上時，才改由父節點的欄位指向它。只要拿到 root，就能沿著 left、right 找到整棵樹。節點若是在執行期間動態配置的，不再使用時也要逐一釋放記憶體。

兩種表示法的比較如下：

小結

為什麼要學二元樹？因為它把「每個節點最多兩個有次序的子節點」固定下來，每個節點都只需要左、右兩個連結，結構單純，也容易在程式中實作。Day 13 的左子右兄弟表示法也說明，一般樹同樣能用兩個連結欄位存放，所以學會二元樹，就掌握了處理樹狀資料的共同基礎。今天整理的傾斜、完美與完整二元樹、節點數的上限與 n₀ = n₂ + 1，以及陣列和鏈結兩種建立方式，都是後續主題的前提：走訪要在這樣的結構上逐一處理節點；累堆會把完整二元樹存進陣列；二元搜尋樹則替左右子樹加上大小規則，讓搜尋時能依資料大小決定往左或往右找。

今日重點：

• 二元樹的左右子節點位置有次序；一邊空著時，另一邊仍保留原來的位置。
• 完美二元樹每層填滿；完整二元樹的最底層可以不滿，但節點必須靠左連續排列。
• 第 i 層最多 2^(i−1) 個節點；高度 h 的非空二元樹最多 2^h − 1 個節點；非空二元樹的葉節點數 n₀ = n₂ + 1。
• 陣列表示法中，索引 i 的左、右子節點在 2i、2i + 1，父節點在 i / 2；傾斜樹會浪費大量空間。
• 鏈結表示法的節點有 left、data、right 三個欄位，空的子節點位置以 NULL 表示。

今天我們迷宮已經蓋好了，下一篇就要真正走進去：學習二元樹的走訪，看看怎麼安排路線，才能把每個路口都拜訪一次，不漏掉也不重複。