Trees

歡迎來到進階資料結構：樹！

各位未來的電腦科學家，大家好！你們已經掌握了陣列、佇列和堆疊等基礎資料結構。現在，我們將進入「階層式」資料的世界。本章節關於樹 (Trees) 的內容至關重要，因為樹是儲存和組織資訊以實現超高效搜尋與排序的最強大工具之一。

如果初看覺得有點複雜，請別擔心。試著把樹不僅看作一個數學概念，而是你每天都在使用的結構，例如電腦中的檔案系統或家譜。我們將會拆解這些術語，並專注於 9645 課程大綱要求的核心概念。讓我們開始吧！

快速回顧：什麼是樹？（基本定義）

在深入細節之前，了解樹是從圖論 (Graphs)（你在 3.10.1 節已學習過）衍生出的一種特殊結構會很有幫助。

樹 (Tree) 的正式定義為：一個連通、無循環的無向圖。

• 連通 (Connected)： 你可以從任何一個節點到達其他任何節點。
• 無向 (Undirected)： 連接（邊）沒有箭頭；移動可以是雙向的。
• 無循環 (No Cycles)： 沒有迴路或封閉路徑。如果你從一個節點出發並沿著邊走，在不回溯的情況下，你無法回到該節點。

你知道嗎？ 雖然一般的「樹」沒有指定的起點，但在電腦科學（特別是考試中）使用的大多是根樹 (Rooted Trees)。

4.1 根樹與重要術語 (課程大綱 3.10.2)

4.1.1 定義根樹

根樹 (Rooted Tree) 是指其中有一個特定頂點（節點）被指定為根 (Root) 的樹。這個簡單的指定建立了清晰的階層，並引入了重要的關係。

根樹的主要特徵：

1. 根 (Root) 是唯一沒有父節點的節點。
2. 所有其他節點都是根的後代 (Descendants)。
3. 該結構建立了節點之間的父子關係 (Parent-child relationships)。

類比： 想像組織結構圖頂端的執行長或創辦人。他們就是根，而其他所有人都隸屬於他們之下。

4.1.2 重要的樹術語

你必須熟悉以下術語：

• 節點 (Node 或 Vertex)： 樹中儲存資料的元素。
• 邊 (Edge 或 Arc)： 兩個節點之間的連線。
• 根 (Root)： 樹的起始節點（沒有父節點）。
• 父節點 (Parent)： 擁有指向其下方節點分支的節點。
• 子節點 (Child)： 位於另一個節點（其父節點）之下的節點。
• 葉節點 (Leaf Node 或 Terminal Node)： 沒有子節點的節點。它們位於分支的「末端」。
• 子樹 (Subtree)： 樹的一部分，本身也是一棵以原樹其中一個節點為根的樹。
• 祖先/後代 (Ancestor/Descendant)： 從根節點到節點 X 的路徑上所有的節點都是 X 的祖先。節點 X 下方的所有節點都是其後代。

4.2 二元樹與二元搜尋樹 (BST)

4.2.1 二元樹 (課程大綱 3.10.2)

二元樹 (Binary Tree) 是一種特殊的根樹，其定義受限於連接數量的嚴格規則：

定義： 一種每個節點最多只有兩個子節點的根樹。

這兩個子節點通常被區分為左子節點 (left child) 和右子節點 (right child)。如果一個節點只有一個子節點，則必須指定它是左子節點或右子節點。

4.2.2 二元搜尋樹 (BST) (課程大綱 3.10.2)

一般的二元樹僅規定結構（最多兩個子節點），而二元搜尋樹 (Binary Search Tree, BST) 則規定了順序。正是這種排序規則使它們在快速資料檢索中顯得極其有用。

定義： 一種二元樹，對於任何給定節點，其左子樹中的所有值都小於該節點的值，且其右子樹中的所有值都大於該節點的值。

BST 規則：

• 左子節點 < 父節點
• 右子節點 > 父節點

常見錯誤： 該規則適用於整個子樹，而不僅僅是直接的子節點。例如，左子樹中的玄孫節點也必須小於根節點。

為什麼要使用 BST？
BST 極大地加快了搜尋速度。如果你要尋找數字 50，而根節點是 75，你立刻知道只需要檢查左子樹。這一步驟就排除了大約一半的資料，這與在已排序陣列上進行「二元搜尋」的方法類似，使得搜尋時間非常高效（對數複雜度，\(O(\log n)\)）。

4.3 樹的遍歷演算法 (課程大綱 3.11.2)

樹的遍歷 (Tree Traversal) 是指以系統化的順序訪問（處理或檢查）樹中每個節點且僅訪問一次的過程。不同於線性結構（如串列或佇列）只有一種明顯的順序，樹有許多遍歷方式，但我們根據父節點在輸出序列中的相對位置，重點關注三種主要類型。

4.3.1 三種遍歷方法

這三種方法通常都以遞迴方式實作（子程序呼叫自身），因為定義可以自然地應用於節點及其子樹。

要記住這三種類型，請關注父節點 (Parent, P) 相對於其左子節點 (Left, L) 和右子節點 (Right, R) 的訪問時機：

1. 前序遍歷 (Pre-order Traversal: P L R)
在子節點之前訪問當前節點（根/父節點）。

步驟：
1. 訪問根節點（處理資料）。
2. 遞迴遍歷左子樹。
3. 遞迴遍歷右子樹。

2. 中序遍歷 (In-order Traversal: L P R)
在左子節點和右子節點之間訪問當前節點（父節點）。

步驟：
1. 遞迴遍歷左子樹。
2. 訪問根節點（處理資料）。
3. 遞迴遍歷右子樹。

3. 後序遍歷 (Post-order Traversal: L R P)
在兩個子節點之後訪問當前節點（父節點）。

步驟：
1. 遞迴遍歷左子樹。
2. 遞迴遍歷右子樹。
3. 訪問根節點（處理資料）。

4.3.2 遍歷追蹤（逐步範例）

想像一棵小型的 BST：
       50 (Root)
      /    \
     25    75

前序遍歷 (P L R) 追蹤：
1. 從 50 (P) 開始。輸出 50。
2. 向左 (L) 移動到 25。輸出 25。
3. 從 25 向左（無）。從 25 向右（無）。
4. 回到 50。向右 (R) 移動到 75。輸出 75。
結果： 50, 25, 75

中序遍歷 (L P R) 追蹤：
1. 從 50 (P) 開始。向左 (L) 移動到 25。
2. 從 25，向左 (L)（無）。
3. 輸出 25 (P)。
4. 從 25 向右 (R)（無）。
5. 回到 50。輸出 50 (P)。
6. 向右 (R) 移動到 75。從 75 向左（無）。
7. 輸出 75 (P)。
結果： 25, 50, 75

重要連結： 使用中序遍歷 (L P R) 追蹤 BST，輸出的元素總是呈遞增順序。這是中序遍歷的主要應用場景。

後序遍歷 (L R P) 追蹤：
1. 從 50 (P) 開始。向左 (L) 移動到 25。
2. 從 25，向左 (L)（無）。向右 (R)（無）。
3. 輸出 25 (P)。
4. 回到 50。向右 (R) 移動到 75。
5. 從 75，向左 (L)（無）。向右 (R)（無）。
6. 輸出 75 (P)。
7. 回到 50。輸出 50 (P)。
結果： 25, 75, 50

4.4 樹遍歷的用途 (課程大綱 3.11.2)

根據你需要執行的任務，不同的遍歷方法各有優劣。

4.4.1 中序遍歷的應用

主要用途是針對二元搜尋樹 (BST)：

1. 以遞增順序輸出 BST 的內容。

4.4.2 前序遍歷的應用

由於父節點最先被訪問，此方法適合在處理細節前先建立結構。

1. 複製樹： 如果以「前序」遍歷，你會先建立根節點，然後是左分支，最後是右分支，這正是重建複本所需的順序。
2. 產生前綴運算式 (Prefix expression)： 這適用於運算式樹，運算子放置在運算元之前（例如 \(+ A B\)）。

4.4.3 後序遍歷的應用

由於父節點最後才被訪問，此方法常用於需要先處理所有子節點，才能操作（或銷毀）父節點的任務。

1. 清空或刪除樹： 你必須先刪除所有子節點（葉節點），才能刪除父節點（否則會先失去對子節點的存取權）。後序遍歷確保刪除操作從最底層開始。
2. 產生後綴運算式 (Postfix expression)： 這適用於運算式樹，運算子放置在運算元之後（例如 \(A B +\)）。這也被稱為反向波蘭表示法 (RPN)。