摘要訊息 : 像樹一樣的資料結構.

0. 前言

在本篇文章中, 我們將介紹第一個非線性的資料結構.

更新紀錄 :

• 2022 年 6 月 7 日進行第一次更新和修正.

1. 定義

定義 1. 若向量 \boldsymbol {\alpha}_{0} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{n} : n > 0 \right \} 的擴展 \mathcal {T} = \left \{ \left ( \alpha_{1}, (p_{1}, c_{1}^{1}, c_{2}^{1}, ..., c_{m_{1}}^{1}) \right ), \left ( \alpha_{2}, (p_{2}, c_{1}^{2}, c_{2}^{2}, ..., c_{m_{2}}^{2}) \right ), ..., \left ( \alpha_{n}, (p_{n}, c_{1}^{n}, c_{2}^{n}, ..., c_{m_{n}}^{n}) \right ) \right \} 滿足

• 必定存在且僅存在一個 p_{k} = \infty (k = 1, 2, ..., n);
• 從任意 \left ( \alpha_{i}, (p_{i}, c_{1}^{i}, c_{2}^{i}, ..., c_{m_{i}}^{i}) \right ) 出發都不存在回到 \left ( \alpha_{i}, (p_{i}, c_{1}^{i}, c_{2}^{i}, ..., c_{m_{i}}^{i}) \right ) 的路徑,

那麼我們稱 \mathcal {T} 為樹 (tree). 其中, \left ( \alpha_{i}, (p_{i}, c_{1}^{i}, c_{2}^{i}, ..., c_{m_{i}}^{i}) \right ) 稱為樹的節點 (node), (p_{i}, c_{1}^{i}, c_{2}^{i}, ..., c_{m_{i}}^{i}) 是節點 \left ( \alpha_{i}, (p_{i}, c_{1}^{i}, c_{2}^{i}, ..., c_{m_{i}}^{i}) \right ) 的指向型標記組 (指向型標記見《【資料結構】前向連結串列》第 1 節), m_{i} 是指向型標記組中除去 p_{i} 之外的指向型標記的數量, p_{i} 指向父節點 (parent node), c_{j}^{i} 指向子節點 (child node), i = 1, 2, ..., n 且 j = 1, 2, ..., m_{i}.

在不引起歧異的情況下, 我們會把節點 \left ( \alpha_{i}, (p_{i}, c_{1}^{i}, c_{2}^{i}, ..., c_{m_{i}}^{i}) \right ) 簡稱為節點 \alpha_{i}. 在 Figure 1 中, 節點 \alpha_{2} 的父節點是 \alpha_{1}, 其子節點有 \alpha_{5} 和 \alpha_{6}. 在 Figure 1 中, 我們沒有明確畫出指向型標記, 而是用一根直線來替代. 例如 \alpha_{3} 和 \alpha_{7} 之間的連線, 實際上有兩重含義. 一個是 \alpha_{3} 的指向型標記 c_{1}^{3}, 另一個是 \alpha_{7} 的指向型標記 p_{7}. 顯然, c_{1}^{3} = \left ( \alpha_{7}, (p_{7}, c_{1}^{7}, c_{2}^{7}) \right ) 且 p_{7} = \left ( \alpha_{3}, (p_{3}, c_{1}^{3}) \right ).

另外, 由定義 1 中的 n > 0 可以看出, 樹不允許為空.

定義 2. 我們稱樹 \mathcal {T} 中滿足 p_{k} = \infty 的第 k 個節點為樹 \mathcal {T} 的根節點 (root node).

在 Figure 1 中, 節點 \alpha_{1} 滿足 p_{1} = \infty, 剩餘節點都不滿足父節點指向型標記為 \infty, 因此節點 \alpha_{1} 便是 Figure 1 樹中的根節點.

定義 3. 我們稱樹 \mathcal {T} 中滿足 m_{i} = 0 的節點為葉子節點 (leaf node).

根據定義 3, 簡單地說, 只要某個節點不擁有子節點, 那麼這個節點就是葉子節點. 在 Figure 1 中, \alpha_{6}, \alpha_{8}, \alpha_{9}, \alpha_{11}, \alpha_{12}, \alpha_{13}, \alpha_{15}, \alpha_{16}, \alpha_{17} 和 \alpha_{19} 都是葉子節點, 因為它們都不存在子節點.

定義 4. 我們稱樹 \mathcal {T} 中滿足 p_{i} = p_{j} 的兩個節點 \left ( \alpha_{i}, (p_{i}, c_{1}^{i}, c_{2}^{i}, ..., c_{m_{i}}^{i}) \right ) 和 \left ( \alpha_{j}, (p_{j}, c_{1}^{j}, c_{2}^{j}, ..., c_{m_{j}}^{j}) \right ) 為兄弟節點 (brother node). 其中, i \neq j.

根據定義 4, 簡單地說, 只要兩個節點擁有相同的父節點, 那麼這兩個節點就是兄弟節點. 例如在 Figure 1 中, \alpha_{2}, \alpha_{3} 和 \alpha_{4} 都是兄弟節點, 因為它們的父節點都是 \alpha_{1}.

定義 5. 對於樹 \mathcal {T} = \left \{ \left ( \alpha_{1}, (p_{1}, c_{1}^{1}, c_{2}^{1}, ..., c_{m_{1}}^{1}) \right ), \left ( \alpha_{2}, (p_{2}, c_{1}^{2}, c_{2}^{2}, ..., c_{m_{2}}^{2}) \right ), ..., \left ( \alpha_{n}, (p_{n}, c_{1}^{n}, c_{2}^{n}, ..., c_{m_{n}}^{n}) \right ) \right \}, 若記 m = \max \left \{ m_{1}, m_{2}, ..., m_{n} \right \}, 那麼我們稱樹 \mathcal {T} 為 m 元樹.

根據定義 5, 簡單地說, 樹中哪一個節點的子節點最多, 若該節點有 m 個子節點, 那麼這棵樹就是 m 元樹. 例如在 Figure 1 中, 子節點數量最多的是 \alpha_{1} 和 \alpha_{4}, 它們都有三個子節點, 所以 Figure 1 中的樹就是三元樹.

定義 6. 我們記樹 \mathcal {T} 中任意節點 \left ( \alpha_{i}, (p_{i}, c_{1}^{i}, c_{2}^{i}, ..., c_{m_{i}}^{i}) \right ) 的度 (degree) 為 m_{i}.

定義 7. 設樹 \mathcal {T} 中葉子節點的集合為 \left \{ \left ( \alpha_{i_{1}}, (p_{i_{1}}) \right ), \left ( \alpha_{i_{2}}, (p_{i_{2}}) \right ), ..., \left ( \alpha_{i_{k}}, (p_{i_{k}}) \right ) \right \}. 其中, k 是樹 \mathcal {T} 中葉子節點的數量. 記根節點 r 到 \left ( \alpha_{j}, (p_{j}) \right ) 的路徑為 h(r, \alpha_{j}) (j = i_{1}, i_{2}, ..., i_{k}), l = \max \left \{ h(r, \alpha_{i_{1}}), h(r, \alpha_{i_{2}}), ..., h(r, \alpha_{i_{k}}) \right \} + 1. 我們稱 l 為樹 \mathcal {T} 的級 (level) 或者高度 (height).

簡單來說, 樹的級就是樹有幾層. 像 Figure 1 中的樹從上到下共有 6 層, 那麼這棵樹的級便是 6. 顯然, 任意樹的第一級只有一個節點, 也就是根節點.

定義 8. 任取樹 \mathcal {T} = \left \{ \left ( \alpha_{1}, (p_{1}, c_{1}^{1}, c_{2}^{1}, …, c_{m_{1}}^{1}) \right ), \left ( \alpha_{2}, (p_{2}, c_{1}^{2}, c_{2}^{2}, …, c_{m_{2}}^{2}) \right ), …, \left ( \alpha_{n}, (p_{n}, c_{1}^{n}, c_{2}^{n}, …, c_{m_{n}}^{n}) \right ) \right \} 中某一節點 \left ( \alpha_{i}, (p_{i}, c_{1}^{i}, c_{2}^{i}, …, c_{m_{i}}^{i}) \right ), 令 p_{i} = \infty. 顯然, 我們得到了一棵新的樹 \mathcal {T}', 這棵樹以 \left ( \alpha_{i}, (p_{i}, c_{1}^{i}, c_{2}^{i}, …, c_{m_{i}}^{i}) \right ) 為根節點. 我們稱樹 \mathcal {T}' 為樹 \mathcal {T} 的子樹 (sub-tree).

不過我們一般不會按照定義, 嚴格地將 p_{i} 設為 \infty, 而是直接稱其為以 \left ( \alpha_{i}, (p_{i}, c_{1}^{i}, c_{2}^{i}, …, c_{m_{i}}^{i}) \right ) 為根節點的子樹. 特別地, 對於任意樹 \mathcal {T} 來說, 我們可以說 \mathcal {T} 是 \mathcal {T} 的子樹. 這就好像集合子集本身就包含自身那樣.

定義 9. 我們稱樹 \mathcal {T} 中滿足 p_{i} \neq p_{j} 但位於同一級的兩個節點 \left ( \alpha_{i}, (p_{i}, c_{1}^{i}, c_{2}^{i}, ..., c_{m_{i}}^{i}) \right ) 和 \left ( \alpha_{j}, (p_{j}, c_{1}^{j}, c_{2}^{j}, ..., c_{m_{j}}^{j}) \right ) 為堂兄弟節點 (cousin node). 其中, i \neq j.

定義 10. 設 r 為樹 \mathcal {T} 的根節點, 對於樹 \mathcal {T} 中任意節點 \left ( \alpha_{i}, (p_{i}, c_{1}^{i}, c_{2}^{i}, ..., c_{m_{i}}^{i}) \right ), 從 r 出發經過若干個節點可以到達 \left ( \alpha_{i}, (p_{i}, c_{1}^{i}, c_{2}^{i}, ..., c_{m_{i}}^{i}) \right ), 那麼這條路徑上的所有節點都稱為 \left ( \alpha_{i}, (p_{i}, c_{1}^{i}, c_{2}^{i}, ..., c_{m_{i}}^{i}) \right ) 的祖先節點 (ancestor node).

定義 11. 設 \left ( \alpha_{i}, (p_{i}, c_{1}^{i}, c_{2}^{i}, ..., c_{m_{i}}^{i}) \right ) 是樹 \mathcal {T} 中某個節點, 從該節點出發可以到達的任意節點都稱為 \left ( \alpha_{i}, (p_{i}, c_{1}^{i}, c_{2}^{i}, ..., c_{m_{i}}^{i}) \right ) 的子孫節點 (descendant node).

定義 12. 若干棵樹的集合 \mathscr {T} = \left \{ \mathcal {T}_{1}, \mathcal {T}_{2}, ..., \mathcal {T}_{n} \right \} 稱為森林 (forest).

定義 13. 設有平衡條件 B, 若樹 \mathcal {T} 中以任意節點為根節點的子樹都滿足 B, 那麼我們稱這棵樹為平衡樹 (balanced tree).

設 B = \left \{ \text {左右子樹的高度相差不超過 } 1 \right \}, 顯然 Figure 1 中的樹就不滿足 B, 但是其中的子樹, 例如以 \alpha_{2} 和 \alpha_{10} 為根節點的子樹就滿足 B, 那麼就可以稱以 \alpha_{2} 和 \alpha_{10} 為根節點的子樹是滿足平衡條件 B 的平衡樹.

定義 14. 我們稱樹中的任意指向型標記為樹的邊 (edge).

也就是說, 在樹中連結兩個節點之間的線就是樹的邊, 例如 Figure 1 中樹的所有線都是邊.

定義 15. 設 n 和 m 是樹 \mathcal {T} 中的兩個節點, 記 P(n, m) 是從節點 n 出發沿著邊到達節點 m 所需要經過的節點集合 (包含起點 n 和終點 m). 我們稱 P(n, m) 是一條從節點 n 出發到達節點 m 的路徑 (path), 稱 s(n, m) = \mathop {\mathrm {card}}{P(n, m)} - 1 是路徑 P(n, m) 的長度 (length). 若 n 樹 \mathcal {T} 的根節點, 那麼我們可以把 P(n, m) 和 s(n, m) 簡單記為 P(m) 和 s(m).

定義 15 實際上有一個隱含的前提, 就是從樹中任意節點出發, 到達另外一個節點有且唯有一條路徑, 並且這條路徑中一定會包含根節點. 這個前提從定義 1 很容易可以看出. 因為除了根節點之外的任意節點, 其連結上一層的邊只有連結父節點的那一條. 例如在 Figure 1 的樹中, \alpha_{5} 只連結 \alpha_{2}, 並沒有也不可能連結 \alpha_{3} 或者 \alpha_{4}. 如果 \alpha_{5} 和 \alpha_{3} 或者 \alpha_{4} 相連, 那就不再符合定義 1, 這就不是一棵樹了. 那麼根據定義 15, 我們可以看出從 \alpha_{5} 到 \alpha_{3} 的路徑為 P(\alpha_{5}, \alpha_{3}) = \left \{ \alpha_{5}, \alpha_{2}, \alpha_{1}, \alpha_{3} \right \}, 路徑長度 s(\alpha_{5}, \alpha_{3}) = 3. 特別地, P(n, n) = \left \{ n \right \}, s(n, n) = 0.

最後值得一提的是, 如果樹只存在一條路徑, 那麼這棵樹顯然就退化成了連結串列 (《【資料結構】連結串列》). 因此, 連結串列實際上是特殊的樹. 極端地, 指向型標記 c_{j}^{i} 已經指明了哪一個是父節點, 哪一個是子節點, 所以樹可以表示為 \mathcal {T} = \left \{ \left ( \alpha_{1}, (c_{1}^{1}, c_{2}^{1}, ..., c_{m_{1}}^{1}) \right ), \left ( \alpha_{2}, (c_{1}^{2}, c_{2}^{2}, ..., c_{m_{2}}^{2}) \right ), ..., \left ( \alpha_{n}, (c_{1}^{n}, c_{2}^{n}, ..., c_{m_{n}}^{n}) \right ) \right \}. 也就是說, 我們完全可以捨棄指向父節點的那一個指向型標記. 此時, 如果樹中只存在一條路徑的話, 那麼這棵樹就退化成了前向連結串列.

2. 尋訪

對一般的樹來說, 其通用操作不多, 除了插入移除節點之外, 比較重要的就是以不同的方式尋訪樹中全部節點.

2.1 層次尋訪

樹的層次尋訪是指從樹的根節點開始, 從上到下按層完成尋訪, 在每一層的尋訪中, 從左到右尋訪每一層中的元素. 例如 Figure 1 中的樹, 其層次尋訪順序就是 \alpha_{1}, \alpha_{2}, ..., \alpha_{19}.

樹的層次尋訪需要借助佇列 (《【資料結構】佇列》) 的幫助. 一開始, 讓根節點進入佇列, 然後不斷從佇列中取出頭部節點. 一旦頭部節點存在子節點, 那麼就按順序讓其進入佇列的尾部. 尋訪完該節點的元素之後, 就從佇列中移除掉這個節點, 然後重複類似操作直到佇列為空為止.

2.2 先序尋訪

樹的先序尋訪會從根節點開始, 首先尋訪節點中的元素, 然後遞迴地尋訪按從左到右的順序尋訪該節點的子樹.

例題 1. 設 O(\alpha) 是將節點中的元素 \alpha 輸出至螢幕上. 根據 Algorithm 2 對 Figure 1 中的樹進行先序尋訪.

解 :

當接收到 Figure 1 中的樹之後, 首先 O(\alpha_{1}) 會將元素 \alpha_{1} 輸出到螢幕上. 接下來, 依次尋訪以 \alpha_{2}, \alpha_{3} 和 \alpha_{4} 為根節點的子樹. 當尋訪以 \alpha_{2} 為根節點的子樹之後, O(\alpha_{2}) 會將元素 \alpha_{2} 輸出到螢幕上. 接下來尋訪以 \alpha_{5} 和 \alpha_{6} 為根節點的子樹. 當尋訪以 \alpha_{5} 為根節點的子樹時, O(\alpha_{5}) 會將元素 \alpha_{5} 輸出到螢幕上. 然後尋訪以 \alpha_{11} 和 \alpha_{12} 為根節點的子樹. 當尋訪以 \alpha_{11} 為根節點的子樹時, O(\alpha_{11}) 會將元素 \alpha_{11} 輸出到螢幕上. 由於 \alpha_{11} 沒有子節點, 所以結束尋訪以 \alpha_{11} 為根節點的子樹, 現在開始尋訪 \alpha_{5} 的第二棵子樹, 即以 \alpha_{12} 為根節點的子樹. O(\alpha_{12}) 將元素 \alpha_{12} 輸出到螢幕之後, 以 \alpha_{12} 為根節點的子樹尋訪完成. 這樣, 以 \alpha_{5} 為根節點的子樹尋訪完成, 下面回到 \alpha_{2} 的第二棵子樹, 即以 \alpha_{6} 為根節點的子樹. 當 O(\alpha_{6}) 將元素 \alpha_{6} 輸出到螢幕上之後, 以 \alpha_{2} 為根節點的子樹中的全部節點都被尋訪過了. 目前螢幕上的輸出為 \alpha_{1}, \alpha_{2}, \alpha_{5}, \alpha_{11}, \alpha_{12}, \alpha_{6}.

接下來, 以類似的過程尋訪以 \alpha_{3} 和 \alpha_{4} 為根節點的子樹.

最終螢幕上會輸出 \alpha_{1}, \alpha_{2}, \alpha_{5}, \alpha_{11}, \alpha_{12}, \alpha_{6}, \alpha_{3}, \alpha_{7}, \alpha_{13}, \alpha_{14}, \alpha_{17}, \alpha_{18}, \alpha_{19}, \alpha_{4}, \alpha_{8}, \alpha_{9}, \alpha_{10}, \alpha_{15}, \alpha_{16}.

\blacksquare

2.3 後序尋訪

後序尋訪和先序尋訪的差別在於 : 先序尋訪會首先使用 O(\alpha) 對元素進行操作, 然後才遞迴地尋訪子樹; 而後序尋訪會首先遞迴地尋訪子樹, 然後使用 O(\alpha) 對元素進行操作.

例題 2. 設 O(\alpha) 是將節點中的元素 \alpha 輸出至螢幕上. 根據 Algorithm 3 對 Figure 1 中的樹進行後序尋訪.

解 :

使用 Algorithm 3 對 Figure 1 中的樹進行後序尋訪之後, 最終螢幕上會有輸出 : \alpha_{11}, \alpha_{12}, \alpha_{5}, \alpha_{6}, \alpha_{2}, \alpha_{13}, \alpha_{17}, \alpha_{19}, \alpha_{18}, \alpha_{14}, \alpha_{7}, \alpha_{3}, \alpha_{8}, \alpha_{9}, \alpha_{15}, \alpha_{16}, \alpha_{10}, \alpha_{4}, \alpha_{1}.

\blacksquare

3. 實作

我自己用 C++ 實作了樹 : https://github.com/Jonny0201/data_structure/blob/master/data_structure/tree.hpp, 大家可以參考後自行實作.