章節：樹（Trees）
歡迎！在這個章節中，我們將一起探索樹（Trees）。在計算機科學中，樹並不是公園裡那種長著葉子和樹皮的植物，而是一種組織數據的方式，讓我們能夠極快地搜尋、添加和刪除資訊。如果你曾經在電腦上使用「檔案總管」來查看資料夾，那你其實已經用過樹狀結構了！
如果一開始覺得這些概念有點抽象，別擔心。我們會用簡單的類比一步步拆解，確保你能夠自信地掌握這些知識。
1. 什麼是樹？
從技術層面來說，樹是一種非線性數據結構。與陣列（Array）或列表（List，就像排成一列的人）不同，樹會向不同的方向分支。
關鍵術語
要理解樹，我們需要先學習描述它們的「家族」術語：
- 節點（Node）：樹中的個別數據項目（就像家譜中的一個人）。
- 邊（Edge）：連接兩個節點的連結或線條。
- 根節點（Root）：樹最頂端的節點。每一棵樹都只有一個根節點。
- 父節點（Parent）：擁有連接到下方節點的邊的節點。
- 子節點（Child）：從上方節點延伸出邊所連接到的節點。
- 葉節點（Leaf）：沒有子節點的節點（它位於分支的最末端）。
- 子樹（Subtree）：樹中的一個較小區段，其本身也是一棵樹。
現實生活類比：想像一家公司的架構。執行長（CEO）是根節點。經理是員工的父節點，而員工則是子節點。處於最底層、不需要管理任何人的員工就是葉節點。
快速複習：
• 根節點是唯一沒有父節點的節點。
• 葉節點是唯一沒有子節點的節點。
• 邊連接父節點與子節點。
2. 二元樹（Binary Trees）
二元樹是一種遵循簡單規則的特殊樹：每個節點最多只能有兩個子節點。
想像一個人最多只有兩個孩子。在二元樹中，我們通常將這兩個孩子稱為左子節點（Left Child）和右子節點（Right Child）。
你知道嗎？二元樹的效率非常高。如果你擁有一棵包含 1,000 個項目且完全平衡的二元樹，你只需要大約 10 個步驟就能找到任何特定項目！
二元搜尋樹（Binary Search Trees, BST）
二元搜尋樹是一種二元樹，其中的數據以特定順序排列，使搜尋速度更快。其規則如下：
- 比父節點小的值放在左側。
- 比父節點大的值放在右側。
例子：如果根節點是 10，你想添加 5，它會放在左側。如果你想添加 15，它會放在右側。
關鍵重點：
BST 的黃金法則就是：左小右大（Left is Less, Right is More）。
3. 樹的遍歷（Tree Traversals）
遍歷是一個專業術語，意指「存取樹中的每一個節點一次」。根據我們存取節點的順序不同，會得到不同的結果。你需要掌握三種主要類型：
1. 前序遍歷（Pre-order Traversal）
在此方式中，我們依序存取根節點，然後是左子樹，最後是右子樹。
記憶法：Root（根）在Pre（前面），優先於其他所有項目。
2. 中序遍歷（In-order Traversal）
我們依序存取左子樹，然後是根節點，最後是右子樹。
記憶法：Root（根）在In（中間）。
專業小貼士：如果你對一棵二元搜尋樹執行中序遍歷，輸出的數字將會呈現完美的數值排序！
3. 後序遍歷（Post-order Traversal）
我們依序存取左子樹，然後是右子樹，最後才是根節點。
記憶法：Root（根）在Post（後面），最後處理。
如何輕鬆完成（「外框」技巧）：
如果你有一棵樹的圖表，從根節點的左側開始畫一條連續的線，繞著樹的外圍繞一圈（就像用繩子把它包起來一樣）。
• 前序遍歷：當你經過節點的左側時標記它。
• 中序遍歷：當你經過節點的底部時標記它。
• 後序遍歷：當你經過節點的右側時標記它。
4. 在 BST 中添加與搜尋
在二元搜尋樹中搜尋數值就像玩「猜大小」遊戲一樣。
逐步搜尋：
- 從根節點開始。
- 你要找的值是否等於當前節點？如果是，那就找到了！
- 數值是否較小？前往左子節點並重複步驟 2。
- 數值是否較大？前往右子節點並重複步驟 2。
- 如果你到達了一個無法再往下移動的點（沒有子節點），說明該數值不存在於樹中。
常見錯誤：
學生常忘記在添加節點時，必須遵循搜尋規則，直到找到一個空位（葉節點）。你不能隨便放置！你必須在過程中將它與沿途的每個父節點進行比較。
快速複習方框：
搜尋或添加：
1. 從根節點開始。
2. 進行比較。
3. 較小？往左走。
4. 較大？往右走。
5. 重複直到找到目標或到達空位。
總結檢查清單
檢查你的理解程度：
[ ] 我能定義根節點、父節點、子節點和葉節點嗎？
[ ] 我知道二元樹的每個節點最多只能有 2 個子節點嗎？
[ ] 我能記住搜尋樹的「左小右大」規則嗎？
[ ] 我能執行中序、前序和後序遍歷嗎？
做得好！樹是計算機科學的基礎組成部分。一旦你掌握了「左 vs 右」的邏輯，你就已經攻克了最困難的部分。