歡迎來到樹狀遍歷（Tree Traversals）！
在本章中，我們將探索電腦是如何在「樹」這種資料結構中進行「行走」的。試想一下家譜或是電腦中的檔案系統，這些都是樹！為了對它們進行任何實用的操作——比如搜尋檔案或列印清單——電腦需要一種系統化的方法來走訪每一個節點（node），且確保不會迷路。
如果剛開始覺得有點抽象，別擔心。一旦你掌握了這些「隱藏路徑」的技巧，你很快就能對這些演算法瞭如指掌，甚至連作夢都會走！
先備知識檢查：什麼是樹？
在開始走路前，我們得先知道自己身在何處。在電腦科學中，樹（Tree）是由節點（nodes）與連接它們的邊（edges）所組成的集合。
• 根節點（Root）：最頂端的節點（也就是「老大」）。
• 節點（Nodes）：包含資料的圓圈。
• 子節點（Children）：從父節點延伸出來的節點。
• 二元樹（Binary Tree）：這是一種特殊的樹，每個節點最多只能有兩個子節點（通常稱為左子節點和右子節點）。
三種遍歷方法
「遍歷（Traversal）」這個詞聽起來很專業，其實就是指走訪樹中每一個節點的意思。針對 AQA 課程大綱，你需要掌握三種具體的遍歷方式。這些方法的名稱正正告訴了你，在樹的任何一個子區域中，該在何時走訪根節點（Root）。
1. 前序遍歷（Pre-Order Traversal）
在前序遍歷中，你會在子節點之前（BEFORE）走訪根節點。
順序是：根節點 → 左子節點 → 右子節點。
記憶小撇步：「Pre」即「之前」。根節點總是排在分支之前。
步驟解析：
1. 走訪根節點。
2. 遍歷左子樹。
3. 遍歷右子樹。
實際應用：複製樹狀結構
如果你想複製一棵樹，就得用前序遍歷。你必須先建立父節點，然後才能將子節點連接上去！
2. 中序遍歷（In-Order Traversal）
在中序遍歷中，根節點是在左子節點和右子節點之間（IN BETWEEN）被走訪的。
順序是：左子節點 → 根節點 → 右子節點。
記憶小撇步：「In-order」會產生「In-creasing」（遞增）的順序，這對於二元搜尋樹（BST）非常實用！
步驟解析：
1. 遍歷左子樹。
2. 走訪根節點。
3. 遍歷右子樹。
實際應用：排序
如果你有一棵二元搜尋樹（BST），執行中序遍歷會輸出遞增順序的資料（例如：1, 2, 3... 或 A, B, C...）。
3. 後序遍歷（Post-Order Traversal）
在後序遍歷中，你是在子節點之後（AFTER）才走訪根節點。
順序是：左子節點 → 右子節點 → 根節點。
記憶小撇步：「Post」即「之後」。根節點是你最後才走訪的節點。
步驟解析：
1. 遍歷左子樹。
2. 遍歷右子樹。
3. 走訪根節點。
實際應用：刪除樹與數學運算
• 清空樹：你必須先刪除子節點，才能刪除父節點（否則子節點會變成記憶體中的「孤兒」！）。
• 逆波蘭表示法（RPN）：後序遍歷可用於將標準數學算式轉換成電腦能輕易透過堆疊（stack）計算的格式。
「輪廓法」技巧：如何追蹤任何樹
如果在考試中看到樹，別慌！使用輪廓法（Outline Method）幾秒鐘就能找到答案。想像你畫出一條連續的線，緊貼著樹的外圍，從根節點的左側開始，繞著樹的形狀走一圈。
取得序列的方法：
• 前序（Pre-order）：當你經過節點的左側時，記下該節點的值。
• 中序（In-order）：當你經過節點的底部時，記下該節點的值。
• 後序（Post-order）：當你經過節點的右側時，記下該節點的值。
快速複習：左邊 = 前序，底部 = 中序，右邊 = 後序。
用途總結（課程大綱要求）
你知道嗎？不同的遍歷方式不僅僅是為了好玩，它們在軟體工程中有非常明確的工作任務。以下是你考試時需要記住的重點：
前序（Pre-Order）：用於複製樹狀結構。
中序（In-Order）：用於以遞增順序輸出 BST 的內容。
後序（Post-Order）：用於中綴轉後綴（RPN）轉換，產生後綴表達式，以及清空/刪除樹。
避免常見錯誤
• 搞混左邊與右邊：在所有三種遍歷中，左邊永遠在右邊之前。唯一會改變位置的是根節點。
• 起點錯誤：無論演算法指示先去哪裡，務必永遠從根節點（最頂端）開始你的追蹤。
• 忽略葉節點（Leaf Nodes）：必須走訪每一個節點，即使是那些位於最底部且沒有子節點的節點也要走訪！
重點整理方塊
前序（Pre-Order）：根-左-右（複製）
中序（In-Order）：左-根-右（排序/BST）
後序（Post-Order）：左-右-根（RPN/刪除）
Big-O 複雜度：這三種遍歷的時間複雜度皆為 \(O(n)\)，因為你必須精確地走訪每一個節點一次。