Tree algorithms

歡迎來到進階演算法：樹狀演算法 (Tree Algorithms)！

大家好！本章節將深入探討計算機科學中最強大且最基本的非線性數據結構之一：樹 (Tree)。你可能會覺得樹只是簡單的圖示，但在演算法層面上，它們對於高效地組織數據至關重要。

在本節中，我們將專注於理解特定類型樹（特別是二元樹 Binary Tree）的結構，並掌握樹狀遍歷 (Tree Traversal) 這項核心技能——即我們用來訪問樹中每個項目的方法。這些演算法是許多複雜數據處理系統（從資料庫到編譯器）的基石。

如果一開始覺得有點棘手，別擔心！我們會使用清晰的步驟和助記法，讓這些演算法的追蹤變得簡單明瞭。讓我們開始吧！

1. 快速複習：什麼是樹？ (3.10.2)

在對樹執行演算法之前，我們先快速鞏固「數據結構」章節中的定義。

A. 定義樹

在計算機科學中，樹是一種特殊的圖（用於表示複雜關係的數據結構），其特徵有兩點：

• 它是連通的 (Connected)：你可以從任何節點到達其他任何節點。
• 它沒有環 (No cycles)：你無法在不回溯的情況下，從某個節點出發並回到同一個節點。

B. 有根樹與二元樹

雖然任何滿足上述標準的結構都是樹，但我們通常處理的是有根樹 (Rooted Tree)，它引入了階層（父子關係）。

• 有根樹：一個明確指定某個節點為根 (Root) 的樹。
  • 根是唯一沒有父節點的節點。
  • 所有其他節點都是根的後代。
  • 位於給定節點下方的節點是它的子節點 (Children)。
• 二元樹 (Binary Tree)：一種有根樹，其中每個節點最多只有兩個子節點。這些子節點通常被稱為左子節點 (Left child) 和右子節點 (Right child)。

---

重點摘要：樹是階層式、無環的結構。我們主要關注的是二元樹。

---

2. 二元搜尋樹 (BST)

二元樹最常見且最有用的應用之一就是二元搜尋樹 (Binary Search Tree, BST)。這種特定的結構可以實現極高效率的搜尋、插入和刪除。

二元搜尋樹 (BST) 的屬性

對於 BST 中的每個節點：

• 所有位於左子樹 (Left Subtree) 的數據值都小於該節點本身的值。
• 所有位於右子樹 (Right Subtree) 的數據值都大於該節點本身的值。

你知道嗎？ 由於這些嚴格的排序規則，BST 是下面其中一種遍歷演算法的完美對象。

3. 樹狀遍歷演算法 (3.11.2)

樹狀遍歷 (Tree Traversal) 是指依照特定順序，恰好訪問樹中每個節點一次的過程。不同於擁有自然線性順序的列表或陣列，樹可以透過多種不同的序列進行處理。

三種主要的遞迴遍歷演算法，定義取決於中央節點 (Node/Root) 相對於其左子樹 (Left/L) 和右子樹 (Right/R) 處理的先後順序。

A. 前序遍歷 (Pre-order Traversal: NLR - 節點、左、右)

在前序遍歷中，你首先訪問節點 (Node/Root)，接著遞迴訪問左子樹，最後遞迴訪問右子樹。

步驟追蹤（「節點優先」規則）

1. 訪問節點 (N)（處理數據）。
2. 遞迴遍歷左子樹 (L)。
3. 遞迴遍歷右子樹 (R)。

記憶小撇步：前序 (Pre-order) 代表根節點是被優先 (Prioritised) 處理且被預先 (Pre-emptively) 訪問的。

前序遍歷的應用 (3.11.2)

• 複製樹：如果你想建立一棵結構完全相同的樹，先處理根節點能確保結構被精確重建。
• 產生前序運算式 (波蘭標記法)：對運算式樹進行前序遍歷，產生的運算式中運算子位於運算元之前（例如 \(+ \ A \ B\)）。

B. 中序遍歷 (In-order Traversal: LNR - 左、節點、右)

在中序遍歷中，你先訪問左子樹，然後訪問節點 (Node/Root)，最後訪問右子樹。

步驟追蹤（「節點在中間」規則）

1. 遞迴遍歷左子樹 (L)。
2. 訪問節點 (N)（處理數據）。
3. 遞迴遍歷右子樹 (R)。

記憶小撇步：中序 (In-order) 把根節點放在左右訪問的 IN（中間）。

中序遍歷的應用 (3.11.2)

這是最著名的應用，特別針對 BST：

• 以升序輸出二元搜尋樹 (BST) 的內容：由於 BST 的定義是「左 < 節點 < 右」，以 LNR 順序訪問節點會自然地按照已排序（升序）的序列輸出數據。

C. 後序遍歷 (Post-order Traversal: LRN - 左、右、節點)

在後序遍歷中，你在訪問節點 (Node/Root) 本身之前，會先遞迴訪問左子樹和右子樹。

步驟追蹤（「節點最後」規則）

1. 遞迴遍歷左子樹 (L)。
2. 遞迴遍歷右子樹 (R)。
3. 訪問節點 (N)（處理數據）。

記憶小撇步：後序 (Post-order) 代表根節點是被推遲 (POSTponed) 到最後才處理的。

後序遍歷的應用 (3.11.2)

• 清空樹（刪除）：要安全地刪除一棵樹，必須先刪除子節點，再刪除父節點。後序遍歷保證你先處理葉節點，一路向上到根節點。
• 產生後序運算式 (反向波蘭標記法)：對運算式樹進行後序遍歷，產生的運算式中運算子位於運算元之後（例如 \(A \ B \ +\)）。

---

4. 追蹤樹狀遍歷

追蹤 (Tracing) 是你需要掌握的實踐技能。請記住，這些是遞迴演算法：你必須對當前節點及其所有子樹應用相同的規則（NLR、LNR 或 LRN）。

想像一棵節點包含字母的簡單二元樹：
根節點 A（B 和 C 的父節點）
B（D 和 E 的父節點）
C（葉節點）
D（葉節點）
E（葉節點）
結構：A 是根。左子節點是 B，右子節點是 C。B 的子節點是 D（左）和 E（右）。

A. 追蹤前序 (NLR)

從 A (根) 開始。

1. N: 訪問 A。(輸出：A)
2. L: 移至左方的 B。對 B 應用 NLR。
   1. N: 訪問 B。(輸出：A, B)
   2. L: 移至左方的 D。對 D 應用 NLR。
      1. N: 訪問 D。(輸出：A, B, D)
      2. L/R: D 沒有子節點。返回。
   3. R: 移至右方的 E。對 E 應用 NLR。
      1. N: 訪問 E。(輸出：A, B, D, E)
      2. L/R: E 沒有子節點。返回。
3. R: 從 A 移至右方的 C。對 C 應用 NLR。
   1. N: 訪問 C。(輸出：A, B, D, E, C)
   2. L/R: C 沒有子節點。返回。

最終前序序列： A, B, D, E, C

B. 追蹤中序 (LNR)

從 A (根) 開始。

1. L: 移至左方的 B。對 B 應用 LNR。
   1. L: 移至左方的 D。對 D 應用 LNR。
      1. L: D 沒有左子節點。
      2. N: 訪問 D。(輸出：D)
      3. R: D 沒有右子節點。返回 B。
   2. N: 訪問 B。(輸出：D, B)
   3. R: 移至右方的 E。對 E 應用 LNR。
      1. L: E 沒有左子節點。
      2. N: 訪問 E。(輸出：D, B, E)
      3. R: E 沒有右子節點。返回 A。
2. N: 訪問 A。(輸出：D, B, E, A)
3. R: 移至右方的 C。對 C 應用 LNR。
   1. L: C 沒有左子節點。
   2. N: 訪問 C。(輸出：D, B, E, A, C)
   3. R: C 沒有右子節點。返回。

最終中序序列： D, B, E, A, C

注意：如果這是 BST 中的數字，這個序列就會是排序好的！

C. 追蹤後序 (LRN)

從 A (根) 開始。

1. L: 移至左方的 B。對 B 應用 LRN。
   1. L: 移至左方的 D。對 D 應用 LRN。
      1. L/R: D 沒有子節點。
      2. N: 訪問 D。(輸出：D)
      3. 返回 B。
   2. R: 移至右方的 E。對 E 應用 LRN。
      1. L/R: E 沒有子節點。
      2. N: 訪問 E。(輸出：D, E)
      3. 返回 B。
   3. N: 訪問 B。(輸出：D, E, B)
   4. 返回 A。
2. R: 移至右方的 C。對 C 應用 LRN。
   1. L/R: C 沒有子節點。
   2. N: 訪問 C。(輸出：D, E, B, C)
   3. 返回 A。
3. N: 訪問 A。(輸出：D, E, B, C, A)

最終後序序列： D, E, B, C, A

---

重點摘要：遞迴遍歷的追蹤涉及到對當前節點應用三步規則 (L, N, R)，如果該步驟又是子樹遍歷，則需立即跳轉到該左子樹或右子樹並重複此過程。

---

5. 實作樹狀遍歷（概念篇）

雖然考試可能不會要求你寫出這些複雜演算法的完整程式碼，但理解其概念性實作（通常以遞迴方式完成）至關重要。

遞迴結構

這三種遍歷通常遵循相似的遞迴藍圖，即依賴子程序對左右子節點執行自我呼叫。

前序遍歷的偽代碼 (Pseudocode) 結構範例：

        
    SUBROUTINE PreOrder(Node)
        IF Node IS NOT NULL THEN
            // 1. 訪問節點 (N)
            OUTPUT Node.Data
            // 2. 遍歷左子樹 (L)
            PreOrder(Node.LeftChild)
            // 3. 遍歷右子樹 (R)
            PreOrder(Node.RightChild)
        END IF
    END SUBROUTINE
        
    

若要改為中序遍歷，只需將 OUTPUT Node.Data 這行移動到左右兩個子程序呼叫之間。

若要改為後序遍歷，則將 OUTPUT Node.Data 這行移動到兩次遞迴呼叫之後。

---

重點摘要：實作依賴於遞迴，其中「訪問節點」步驟的位置決定了遍歷的類型。

---