1. 定義

定義 1. 一棵二元樹 T 是有限個元素的集合 (可以為空). 當二元樹非空時, 其中有一個元素 t 作為樹的根, 餘下的元素 (若存在) 被劃分為兩顆二元樹, 分別是 t 的左子樹和右子樹.

一般來說, 如果一棵二元樹的根為 t, 我們可以直接以 t 來代表這棵二元樹.

二元樹和樹的根別區別有以下幾點 :

  • 二元樹中的每個元素至多只能有兩顆子樹; 但是, 樹可以有無限個子樹;
  • 在二元樹中, 每個元素的子樹都是有序的, 分別是左子樹和右子樹;  但是, 樹的任何子樹都是無序的, 沒有左右子樹之分;
  • 樹不可以為空, 而二元樹可以為空.

2. 性質

性質 1. 若一棵二元樹有 n 個元素, 那麼它必定有 n - 1 條邊. 其中, n > 0.

證明 :

一棵二元樹中, 除了根節點之外, 每一個子節點都有且唯有一個父節點. 因此, 除根節點之外的剩餘 n - 1 個節點共有 n - 1 條邊和其父節點相連結, 而根節點沒有父節點. 故若一棵二元樹有 n 個元素, 那麼它必定有 n - 1 條邊. 其中, n > 0.

\blacksquare

性質 2. 若一棵二元樹的高度為 h, 則它至少有 h 個元素, 至多有 2^{h} - 1 個元素. 其中, h \geq 0.

證明 :

首先, 對於一棵高度為 h 的二元樹, 每一層都至少有一個元素, 因此至少有 h 個元素.

考慮到二元樹中一個父節點至多攜帶兩個子節點, 因此第 i 層至多有 2^{i - 1} 個節點, i = 1, 2, ..., h. 當 h = 0 時, 元素的總數為 0, 即 2^{0} - 1 = 0; 當 h > 0 時, 元素的總數為 \displaystyle {\sum \limits_{i = 1}^{h}2^{i - 1} = 2^{h} - 1} 個.

因此, 若一棵二元樹的高度為 h, 則它至少有 h 個元素, 至多有 2^{h} - 1 個元素. 其中, h \geq 0.

\blacksquare

性質 3. 若一棵二元樹有 n 個元素, 那麼其高度最大為 n, 最小為 \left \lceil \log_{2} {(n + 1)} \right \rceil.

證明 :

性質 2 可以知道, 若每一層有且唯有一個元素, 那麼此時樹的高度即為 n, 且不會超過 n.

再由性質 2 可知, 高度為 h 的二元樹至多有 2^{h} - 1 個元素. 由於 n \leq 2^{h} - 1, 因此有 h \geq \log_{2} {(n + 1)}. 由於 h 是整數, 因此 h \geq \left \lceil \log_{2} {(n + 1)} \right \rceil.

\blacksquare

定義 2. 對於一棵高度為 h 的二元樹, 若其恰好有 2^{h} - 1 個元素, 則稱這棵樹為滿二元樹.

定義 3. 對高度為 h 的滿二元樹進行編號, 編號的順序為從上到下依次, 然後從左至右按順序進行編號. 從 12^{h} - 1. 假設從滿二元樹的最後一層級從最後一個元素開始向前刪除 k 個元素, 所得的二元樹稱為完全二元樹.

例題 1. 從一棵高度為 3 的滿二元樹中刪除 1 個, 2 個和 3 個元素, 使得滿二元樹刪除這些元素之後成為一棵完全二元樹.

\blacksquare

顯然, 滿二元樹是一棵特殊的完全二元樹. 而且完全二元樹最後一層的元素是從左至右進行排列的, 中間不能有斷裂的情況出現 :
否則, 這棵樹就不能成為一棵完全二元樹.

在一棵完全二元樹種, 如果我們按照從上至下為基礎, 然後從左至右進行編號, 那麼一個父節點和子節點的序號是有嚴格關係的 : 設二元樹 T 中某個節點的編號為 i, 則有

  • 如果 i = 1, 則這個節點是二元樹的根節點
  • 如果 i > 1, 則
    1. 這個節點的父節點編號為 \left \lfloor \frac {i}{2} \right \rfloor
    2. 如果 2i \leq n, 則編號為 2i 的節點是這個節點的左子節點
    3. 如果 2i + 1 \leq n, 則編號為 2i + 1 的節點是這個節點的右子節點

利用上面這個特性, 我們可以使用陣列來儲存一棵二元樹 :
但是有些時候, 如果二元樹中的元素不多, 那麼使用陣列來儲存就會浪費很多空間 :
因此, 針對元素比較多的二元樹, 應該使用陣列來儲存. 因為在大多數語言中, 陣列的存取會比連結串列這樣的方式要快得多. 但是, 如果二元樹的高度比較大, 但是元素比較少, 此時應該採用連結串列的形式進行儲存.

3. 尋訪

二元樹的尋訪總共有兩種方式 :

  • 層級尋訪 level-order. 從上到下, 從左至右, 按照編號順序進行尋訪;
  • 次序尋訪. 以固定的次序尋訪元素, 直到所有元素都尋訪完畢為止. 次序尋訪又分為以下三種 :
    1. 前序 pre-order : 首先存取目前節點的元素, 然後前往左子樹, 然後前往右子樹;
    2. 中序 in-order : 首先前往左子樹, 再存取元素, 最後前往右子樹;
    3. 後序 post-order : 首先前往左子樹, 然後前往右子樹, 最後存取元素.

需要注意的是, 前往某個子樹和存取元素是不同的動作. 前往某個子樹的意思是由當前某個節點開始, 向另一個子節點前進, 而不存取這個節點中的元素; 而存取元素只是回傳當前節點中的元素, 而不進行節點的移動. 我們一個實例.

例題 2. 寫出二元樹 T 從根節點開始的尋訪結果.

:

對於層級尋訪, 就是按照從上到下, 從左到右的順序進行尋訪即可, 因此結果為 ABCDEFG.

對於次序尋訪, 實際上是需要遞迴進行的, 因此我們採用堆疊的演示方式. 首先來看前序尋訪 :

  • 開始尋訪. 目前位於根節點. 根據前序尋訪的順序, 我們首先存取元素, 此時結果為 A. 然後前往 A 節點的左子節點 :
    • 現在來到了 B 節點. 根據尋訪順序, 首先存取元素, 此時的結果為 AB. 然後前往 B 節點的左子節點 :
      • 根據尋訪順序, 首先存取元素, 此時的結果為 ABD. 然後嘗試前往 D 節點的左子節點的時候, 發現為空; 然後嘗試前往 D 節點的右子節點的時候, 發現仍然為空. 因此回溯到 B 節點.
    • 現在回到了 B 節點. 跟根據尋訪順序, 接下來要前往 B 節點的右子節點 :
      • 根據尋訪順序, 首先存取元素, 此時的結果為 ABDE. 然後嘗試前往 E 節點的左子節點的時候, 發現為空; 然後嘗試前往 E 節點的右子節點的時候, 發現仍然為空. 因此回溯到 B 節點.
    • 現在又回到了 B 節點, 由於 B 節點的左右子樹都已經尋訪, 因此回溯到 A 節點.
  • 現在回到了 A 節點. 根據前序尋訪的順序, 現在前往 A 節點的右子節點 :
    • 現在來到了 C 節點根據尋訪換序, 首先存取元素, 此時的結果為 ABDEC. 然後嘗試前往 C 節點的左子樹 :
      • 根據尋訪順序, 首先存取元素, 此時的結果為 ABDECF. 然後嘗試前往 F 節點的左子節點的時候, 發現為空; 然後嘗試前往 F 節點的右子節點的時候, 發現仍然為空. 因此回溯到 C 節點.
    • 現在回到了 C 節點. 根據尋訪順序, 接下來要前往 C 節點的右子節點 :
      • 根據尋訪順序, 首先存取元素, 此時的結果為 ABDECFG. 然後嘗試前往 G 節點的左子節點的時候, 發現為空; 然後嘗試前往 G 節點的右子節點的時候, 發現仍然為空. 因此回溯到 C 節點.
    • 現在又回到了 C 節點. 由於 C 節點的左右子樹都已經尋訪, 因此回溯到 A 節點.
  • 現在又回到了 A 節點. 由於 A 節點的左右子樹都已經尋訪, 因此嘗試回到 A 節點的父節點. 由於 A 節點的父節點為空, 代表者 A 節點就是這棵樹的根節點, 故尋訪完畢.

最終前序尋訪的結果為 ABDECFG. 然後來看中序尋訪 :

  • 開始尋訪. 目前位於根節點. 根據中序尋訪的順序, 我們首先前往 A 節點的左子節點 :
    • 現在來到了 B 節點. 根據尋訪順序, 我們前往 B 節點的左子節點 :
      • 現在來到 D 節點. 根據尋訪順序, 我們首先前往 D 節點的左子節點, 但是 D 節點的左子節點為空, 於是回到了 D 節點; 然後, 我們存取 D 節點, 此時的結果為 D; 最後嘗試前往 D 節點的右子節點, 發現右子節點也為空. 此時, D 節點尋訪完畢, 回到 B 節點.
    • 現在回到了 B 節點. 我們要存取 B 節點中的元素, 此時的結果為 DB. 然後嘗試前往 B 節點的右子節點 :
      • 現在來到了 E 節點. 根據尋訪順序, 我們首先前往 E 節點的左子節點, 但是 E 節點的左子節點為空, 於是回到了 E 節點; 然後, 我們存取 E 節點, 此時的結果為 DBE; 最後嘗試前往 E 節點的右子節點, 發現右子節點也為空. 此時, E 節點尋訪完畢, 回到 B 節點.
    • 現在又回到了 B 節點, 由於 B 節點的左右子樹都已經尋訪, 因此回溯到 A 節點.
  • 現在回到了 A 節點. 根據中序尋訪的順序, 存取 A 節點中的元素, 此時的結果為 DBEA. 最後根據尋訪順序, 我們前往 A 節點的右子節點 :
    • 現在來到了 C 節點. 根據尋訪換序, 我們前往 C 節點的左子節點 :
      • 現在來到 F 節點. 根據尋訪順序, 我們首先前往 F 節點的左子節點, 但是 F 節點的左子節點為空, 於是回到了 F 節點; 然後, 我們存取 F 節點, 此時的結果為 DBEAF; 最後嘗試前往 F 節點的右子節點, 發現右子節點也為空. 此時, F 節點尋訪完畢, 回到 C 節點.
    • 現在回到了 C 節點. 存取 C 節點中的元素, 此時的結果為 DBEAFC. 最後根據尋訪順序, 我們前往 C 節點的右子節點 :
      • 現在來到了 G 節點. 根據尋訪順序, 我們首先前往 G 節點的左子節點, 但是 G 節點的左子節點為空, 於是回到了 G 節點; 然後, 我們存取 G 節點, 此時的結果為 DBEAFCG; 最後嘗試前往 G 節點的右子節點, 發現右子節點也為空. 此時, G 節點尋訪完畢, 回到 C 節點.
    • 現在又回到了 C 節點. 由於 C 節點的左右子樹都已經尋訪, 因此回溯到 A 節點.
  • 現在又回到了 A 節點. 由於 A 節點的左右子樹都已經尋訪, 因此嘗試回到 A 節點的父節點. 由於 A 節點的父節點為空, 代表者 A 節點就是這棵樹的根節點, 故尋訪完畢.

最終中序尋訪的結果為 DBEAFCG. 最後來看看後序尋訪 :

  • 開始尋訪. 目前位於根節點. 根據後序尋訪的順序, 我們首先前往 A 節點的左子節點 :
    • 現在來到了 B 節點. 根據尋訪順序, 我們前往 B 節點的左子節點 :
      • 現在來到 D 節點. 根據尋訪順序, 我們首先前往 D 節點的左子節點, 但是 D 節點的左子節點為空, 於是回到了 D 節點; 然後, 嘗試前往 D 節點的右子節點, 發現右子節點也為空; 最後我們存取 D 節點, 此時的結果為 D. 此時, D 節點尋訪完畢, 回到 B 節點.
    • 現在回到了 B 節點. 根據尋訪的順序, 我們前往 B 節點的右子節點
      • 現在來到 E 節點. 根據尋訪順序, 我們首先前往 E 節點的左子節點, 但是 E 節點的左子節點為空, 於是回到了 E 節點; 然後, 嘗試前往 E 節點的右子節點, 發現右子節點也為空; 最後我們存取 E 節點, 此時的結果為 DE. 此時, E 節點尋訪完畢, 回到 B 節點.
    • 現在又回到了 B 節點, 最後我們存取 B 節點的元素, 此時的結果為 DEB. B 節點為根的子樹已經尋訪完畢了, 現在回到 A 節點.
  • 現在回到了 A 節點. 根據後序尋訪的順序, 我們前往 A 節點的右子節點 :
    • 現在來到了 C 節點. 根據尋訪換序, 我們前往 C 節點的左子節點 :
      • 現在來到 F 節點. 根據尋訪順序, 我們首先前往 F 節點的左子節點, 但是 F 節點的左子節點為空, 於是回到了 F 節點; 然後, 嘗試前往 F 節點的右子節點, 發現右子節點也為空; 最後我們存取 F 節點, 此時的結果為 DEBF. 此時, F 節點尋訪完畢, 回到 C 節點.
    • 現在回到了 C 節點. 根據尋訪的順序, 我們要前往 C 節點的右子節點 :
      • 現在來到 G 節點. 根據尋訪順序, 我們首先前往 G 節點的左子節點, 但是 G 節點的左子節點為空, 於是回到了 G 節點; 然後, 嘗試前往 G 節點的右子節點, 發現右子節點也為空; 最後我們存取 G 節點, 此時的結果為 DEBFG. 此時, G 節點尋訪完畢, 回到 C 節點.
    • 現在又回到了 C 節點. 最後我們存取 C 節點的元素, 此時的結果為 DEBFGC. C 節點為根的子樹已經尋訪完畢了, 現在回到 A 節點.
  • 現在又回到了 A 節點. 根據尋訪順序, 我們還要存取 A 節點中的元素. 此時的結果為 DEBFGCA. 由於 A 節點的左右子樹都已經尋訪, 因此嘗試回到 A 節點的父節點. 由於 A 節點的父節點為空, 代表者 A 節點就是這棵樹的根節點, 故尋訪完畢.

最終後續尋訪的結果為 DEBFGCA.

\blacksquare

在程式設計時, 我們一般借助佇列來對二元樹進行層級尋訪; 借助堆疊或者遞迴來對二元樹進行次序尋訪. 以層級尋訪為例, 我們首先讓根節點進入佇列, 然後讓佇列首個元素的左子節點和右子節點分別進入佇列的最後, 然後存取完佇列的首個元素之後, 刪除佇列的頭部元素即可. 不斷重複上述步驟, 直到佇列為空的時候, 尋訪完成. 以使用堆疊進行前序尋訪為例, 我們首先讓根節點進入堆疊. 然後每次取堆疊頂部的元素, 首先存取元素, 然後讓該元素的左子節點進入堆疊, 如果該元素沒有左子節點或者左子樹已經被尋訪, 那麼直接讓右子節點進入堆疊. 不斷重複上述步驟, 直到堆疊為空的時候, 尋訪完成. 對於中序尋訪和後序尋訪, 只是順序不同罷了.

4. 旋轉

二元樹可以以某個節點為基準, 進行左旋轉和右旋轉. 我們首先用文字描述一下左右旋轉.

p 是樹 T 的某個非空節點, cp 的非空右子節點, lc 的左子節點. 對於左旋轉, 就是讓以 p 為根的子樹去替換原來 c 的左子樹 l, 然後將 l 放入到 p 的右子樹當中. 我們使用下面的 SVG 圖像進行演示 :
這看起來以 p 為根的子樹, 以 c 為中心, 隨著 pc 的連接線, 向左自然滑落一樣. 這便是左旋的名稱由來. 被擠掉的 l 節點被重新安排至 p 的右子節點, 因為 p 的右子節點本來是 c, 滑落之後 p 的右子節點總為空. 在之後的平衡樹中, 大家會看到要將 l 安排至 p 的右子節點的又一理由.

右旋轉恰好與左旋轉對稱. 設 p 是樹 T 的某個非空節點, cp 的左子非空節點, rc 的右子節點. 對於右旋轉, 就是讓以 p 為根的子樹去替換原來 c 的右子樹 r, 然後將 l 放入到 p 的左子樹當中. 我們使用下面的 SVG 圖像進行演示 :
這看起來以 p 為根的子樹, 以 c 為中心, 隨著 pc 的連接線, 向右自然滑落一樣. 這便是右旋的名稱由來. 被擠掉的 r 節點被重新安排至 p 的左子節點, 因為 p 的左子節點本來是 c, 滑落之後 p 的左子節點總為空. 在之後的平衡樹中, 大家會看到要將 l 安排至 p 的左子節點的又一理由.

值得注意的是, 我們規定另外兩種旋轉都是不可行的 :
因為這兩種旋轉的角度過大了.

定理 1. 在對二元樹進行旋轉之後, 二元樹的中序尋訪結果不改變.

證明 :

首先證明二元樹在進行左旋轉之後, 中序尋訪結果不發生改變.

p 是二元樹 T 的某個非空節點, cp 的非空右子節點, lc 的左子節點. 記 x 為存取 p 節點元素之前產生的尋訪結果, c_{l} 為節點 c 的左子樹的尋訪結果, y 為存取節點 c 元素之後的尋訪結果, 旋轉過後的二元樹為 T'. 我們直接使用 pc 來表示節點 pc 中的元素. 那麼在進行左旋轉之前, 二元樹 T 的中序尋訪結果為 xpc_{l}cy.

要證明二元樹在左旋轉之後中序尋訪順序不變, 只需要證明二元樹 T 在左旋轉之後的中序尋訪結果仍然為 xpc_{l}cy.

p 為二元樹 T 的根節點, 在二元樹 T 以節點 c 為中心進行左旋轉之後, c 將成為 T' 的根節點. 根據中序尋訪的規則, 我們並不是直接存取 c 中的元素, 而是首先前往 c 的左子樹 p. 而左旋並沒有改變 p 的左子樹, 因此在旋轉之後, x 不改變. 根據中序尋訪的規則, 在存取 p 中的元素之後, 目前的尋訪結果為 xp. 接下來要尋訪 p 的右子樹. 在旋轉之後, p 的右子樹發生了改變, 變成了以 l 為根節點的子樹. 而 c_{l} 是以 l 為根節點的子樹的尋訪結果, 因此可以確定尋訪完 l 之後, 現在的尋訪結果為 xpc_{l}. 現在 c 的左子樹已經尋訪完畢, 要存取 c 中的元素, 於是尋訪結果為 xpc_{l}c. 旋轉並不改變原本位於 c 節點的右子樹, 於是 y 便是以 c 的右子節點為根節點的子樹的尋訪結果. 因此, 總體的尋訪結果為 xpc_{l}cy.

p 不是二元樹 T 的根節點, 我們已經證明了以 p 為根節點的子樹經過旋轉, 變為 c 為根節點之後, 子樹的尋訪順序不改變. 因此, 我們只需要考慮 xy 是否改變即可. 對於 c 的左子樹位於 x 的部分和 p 的右子樹位於 y 的部分, 我們可以由上面的分析可知這兩個部分的尋訪結果不改變. 而左旋只改變了原本以 p 為根節點的子樹, 其餘部分的節點順序並未改變, 因此尋訪結果也不改變. 因此, 尋訪完畢之後的結果仍然為 xpc_{l}cy.

所以在二元樹進行左旋轉之後, 中序尋訪的結果不發生改變.

\square

接下來證明二元樹進行右旋轉之後, 中序尋訪的結果仍然不發生改變.

p 是二元樹 T 的某個非空節點, cp 的非空左子節點, lc 的右子節點. 記 x 為存取 c 節點元素之前產生的尋訪結果, y 為存取 c 節點元素之後產生的尋訪結果, c_{r} 為節點 c 的右子樹的尋訪結果, 旋轉過後的二元樹為 T'. 我們直接使用 pc 來表示節點 pc 中的元素. 那麼在進行左旋轉之前, 二元樹 T 的中序尋訪結果為 xcc_{r}py.

要證明二元樹在左旋轉之後中序尋訪順序不變, 只需要證明二元樹 T 在右旋轉之後的中序尋訪結果仍然為 xcc_{r}py.

p 為二元樹 T 的根節點, 在二元樹 T 以節點 c 為中心進行右旋轉之後, c 將成為 T' 的根節點. 根據中序尋訪的規則, 我們並不是直接存取 c 中的元素, 而是首先前往 c 的左子樹 p. 而左子樹 p 的尋訪結果即是旋轉之前 c 的左子樹的尋訪結果. 旋轉並沒有改變本來位於 c 左子樹中的節點順序, 因此 x 不變, 於是現在的尋訪結果為 x. 根據中序尋訪的順序, 接下來要存取 c 節點中的元素, 於是尋訪結果為 xc. 然後要尋訪 c 的右子樹. 由於旋轉之後, p 成為了 c 的右子樹, 因此需要首先尋訪 p 的左子樹. 而 r 被放置在了 p 的左子節點中, 旋轉並沒有改變以 r 為根節點的子樹的順序, 因此 c_{r} 不發生改變. 於是, 現在的尋訪結果為 xcc_{r}. 接下來要存取 p 節點中的元素, 尋訪結果會變為 xcc_{r}p. 之後就會尋訪 p 的右子節點, 而旋轉也沒有改變其右子樹的順序, 因此尋訪完畢之後結果為 xcc_{r}py.

p 不是二元樹 T 的根節點. 我們已經證明了以 p 為根節點的子樹經過旋轉, 變為 c 為根節點之後, 子樹的尋訪順序不改變. 因此, 我們只需要考慮 xy 是否改變即可. 對於 c 的左子樹位於 x 的部分和 p 的右子樹位於 y 的部分, 我們可以由上面的分析可知這兩個部分的尋訪結果不改變. 而右旋只改變了原本以 p 為根節點的子樹, 其餘部分的節點順序並未改變, 因此尋訪結果也不改變. 因此, 尋訪完畢之後的結果仍然為 xcc_{r}py.

所以在二元樹進行右旋轉之後, 中序尋訪的結果不發生改變.

\square

綜上所述, 在對二元樹進行旋轉之後, 二元樹的中序尋訪結果不改變.

\blacksquare

5. 實作

資料結構 binary_tree : GitHub 點擊直達