歡迎來到樹狀結構的世界！
在本章中，我們將探索樹狀演算法 (Tree Algorithms)。雖然聽到「樹」可能會讓你想起公園裡的綠色植物，但在計算機科學中，它們是組織數據最強大的工具之一。無論是在電腦中搜尋檔案，還是在電子字典中查找單字，背後往往都有樹狀演算法在運作！閱讀完這份筆記後，你將能理解這些結構的運作原理，並像專業人士一樣輕鬆地「走訪」它們。
1. 什麼是樹 (Tree)？
在深入研究演算法之前，我們先快速複習一下什麼是樹。樹 (Tree) 是一種看起來像倒過來的真實樹木的數據結構。它從一個單一點開始，然後向外分支出去。
必須記住的關鍵術語：
節點 (Node)： 樹中的單個元素（通常包含數據，如數字或名稱）。
根節點 (Root)： 樹的最頂端節點。每棵樹都恰好有一個根節點。
邊 (Edge)： 連接節點之間的線或連結。
父節點 (Parent)： 擁有指向其下方節點連結的節點。
子節點 (Child)： 擁有來自上方節點連結的節點。
葉節點 (Leaf)： 沒有任何子節點的節點（樹枝的「盡頭」）。
快速回顧： 除了根節點外，每個節點都恰好有一個父節點，但一個父節點可以擁有多個子節點！
2. 二元搜尋樹 (Binary Search Tree, BST)
二元樹 (Binary Tree) 是一種特殊的樹，其中每個節點最多只能有兩個子節點（通常稱為左子節點和右子節點）。
二元搜尋樹 (BST) 增加了一條非常重要的規則，幫助我們快速找到數據：
1. 比父節點小的數據放在左邊。
2. 比父節點大的數據放在右邊。
為什麼這很有用？
由於這個「左小右大」的規則，搜尋數值的速度會變得非常快。我們不必像查看列表那樣逐一檢查每個項目，而是每次向下移動一層時，都能排除掉一半的樹。平衡二元搜尋樹的搜尋時間效率通常為 \( O(\log n) \)。
重點總結： BST 是為速度而設計的。它將漫長的搜尋過程轉化為一系列簡單的「左還是右？」的決策。
3. 樹的走訪演算法 (Tree Traversal Algorithms)
走訪 (Traversal) 是指以特定順序存取樹中每個節點的專業術語。在 Oxford AQA 9645 的課程大綱中，你需要掌握三種「深度優先 (Depth-First)」的方法。別擔心名稱聽起來很像，我們有個小撇步能幫你記住它們！
方法一：前序走訪 (Pre-order Traversal)
在前序走訪中，我們在存取子節點之前先存取根節點。
順序：根節點 \(\rightarrow\) 左節點 \(\rightarrow\) 右節點
用途： 複製一棵樹，或顯示目錄結構。
方法二：中序走訪 (In-order Traversal)
在中序走訪中，我們在左子節點和右子節點之間存取根節點。
順序：左節點 \(\rightarrow\) 根節點 \(\rightarrow\) 右節點
神奇的事實： 如果你對二元搜尋樹執行中序走訪，你將會以完美的數值或字母順序存取所有節點！
方法三：後序走訪 (Post-order Traversal)
在後序走訪中，我們在存取完所有子節點之後才存取根節點。
順序：左節點 \(\rightarrow\) 右節點 \(\rightarrow\) 根節點
用途： 刪除樹（你必須先刪除子節點才能刪除父節點）或計算數學表達式樹。
記憶技巧 - 「根節點規則」：
- Pre 代表「之前」 \(\rightarrow\) 根節點在最前 (First)。
- In 代表「中間」 \(\rightarrow\) 根節點在中間 (Middle)。
- Post 代表「之後」 \(\rightarrow\) 根節點在最後 (Last)。
4. 走訪的「點點技巧」(The Dot Trick)
如果在考試中需要追蹤走訪過程，請使用這個「秘密方法」。它絕對管用！
第一步： 在樹的每個節點上畫一個小點。
- 若為前序走訪，把點畫在節點的左側。
- 若為中序走訪，把點畫在節點的底部。
- 若為後序走訪，把點畫在節點的右側。
第二步： 想像一支筆從根節點的左側開始，畫出一條持續不斷的線，沿著樹的外緣「環繞」（就像一個人繞著樹邊走一樣）。
第三步： 每當你的線經過一個點，就寫下該節點的值。寫下來的順序就是你的答案！
快速回顧： 這種物理上的「描邊」方法是最安全的方式，能確保你不會遺漏節點或搞混順序。
5. 在 BST 中加入新節點
要將新數據加入二元搜尋樹，我們遵循與搜尋相同的邏輯。我們從根節點開始，將新值與當前節點進行比較。
逐步流程：
1. 樹是空的嗎？如果是，新值將成為根節點。
2. 如果不是，將新值與當前節點比較。
3. 比當前節點小嗎？移動到左子節點。
4. 比當前節點大嗎？移動到右子節點。
5. 重複此過程，直到到達一個空的點（「邊」）。
6. 將你的新節點放在那裡。
常見錯誤： 學生有時會試圖在加入節點時「重新排列」樹。千萬別這麼做！新節點永遠是作為分支末端的一個新的「葉節點」被加入的。
總結：考試關鍵重點
結構： 樹由節點和邊組成。頂端是根節點；末端是葉節點。
BST 規則： 左子節點 \( < \) 父節點；右子節點 \( > \) 父節點。
走訪：
- 前序 (Pre-order)： 根、左、右（用於複製）
- 中序 (In-order)： 左、根、右（用於排序）
- 後序 (Post-order)： 左、右、根（用於刪除）
效率： 在平衡的情況下，搜尋 BST 的效率遠高於線性搜尋，其複雜度為 \( O(\log n) \)。
如果一開始覺得走訪有點混亂，別擔心！試著畫一個有 3 個節點（數字 10、5 和 15）的小樹，練習一下「點點技巧」。只要練習兩次，這就會變成你的直覺！