歡迎來到樹狀結構的世界！

你好！今天我們要深入探討計算機科學中，最重要且優雅的數據組織方式之一：樹 (Trees)。雖然你之前已經接觸過陣列 (arrays) 和堆疊 (stacks) 這類線性結構，但樹是層次化 (hierarchical) 的。這意味著它們非常適合呈現事物之間的從屬關係，例如電腦裡的資料夾或族譜。

如果剛開始覺得這些概念有點抽象，別擔心！我們會一步步拆解，並透過大量生動的比喻，幫助你拓展知識的枝葉！


1. 到底什麼是樹？

在 AQA 課程大綱中，樹有非常具體的數學定義。它是一個連通、無向且無環的圖 (connected, undirected graph with no cycles)。

讓我們把這些專業術語轉化成簡單的說法：

  • 連通 (Connected)： 你可以透過線條從樹的任何一部分到達另一部分，沒有任何「漂浮」在外的節點。
  • 無向 (Undirected)： 線條（邊）沒有箭頭，不指定單一方向。
  • 無環 (No Cycles)： 這點最重要！意即圖中沒有迴路。你不能從一點出發，沿著路徑走，在不回頭的情況下又回到起點。

你知道嗎？ 在數學上，樹其實不需要有「起點」或根節點。但在計算機科學中，我們幾乎總是處理有根樹 (Rooted Trees)。

有根樹的關鍵術語

當我們選定一個節點作為「起點」時，稱之為根節點 (Root)。一旦有了根節點，其他所有節點都會成為它的後代 (descendant)。這就建立了父子關係 (parent-child relationship)：

  • 節點 (Node)： 單一的數據元素（也就是那些「圓圈」）。
  • 邊 (Edge)： 連接兩個節點的線。
  • 根節點 (Root)： 唯一沒有父節點的節點，是位居頂端的「大佬」。
  • 父節點 (Parent)： 擁有指向下方節點的邊的節點。
  • 子節點 (Child)： 由上方節點連接而來的節點。
  • 葉節點 (Leaf)： 沒有任何子節點的節點。它們是樹的「末端」。

重點總結： 樹就是一種連通且無環的圖。在計算機科學中，我們通常指定一個節點為「根節點」來構建層次結構。


2. 二元樹 (Binary Tree)

二元樹 (Binary Tree) 是一種特殊的有根樹，在考試中會經常出現。規則很簡單：每個節點最多只能有兩個子節點。

把它想像成一個家庭，每個人最多只能生兩個小孩。我們通常稱之為「左子節點 (Left Child)」和「右子節點 (Right Child)」。

二元搜尋樹 (Binary Search Tree, BST)

二元樹最常見的應用是二元搜尋樹 (BST)。這是一種為了讓數據搜尋變得極快而特別設計的結構，每個節點都遵循嚴格的規則：

  • 比父節點小的值放在左邊。
  • 比父節點大的值放在右邊。

記憶小撇步： 「左小右大」。如果數字比較小，就往左轉！

快速回顧：二元搜尋樹的效率

由於你在向下移動每一層時，基本上都將剩餘的節點數量減半，因此搜尋平衡二元樹的效率非常高。在大 O 符號 (Big O Notation) 中，搜尋二元樹的時間複雜度為 \(O(\log n)\)。


3. 樹的遍歷 (Tree Traversals)

有時我們需要訪問樹中的每一個節點（例如將它們列印出來或進行複製）。這稱為遍歷 (traversing)。因為樹不是直線的，我們有三種主要方法，這取決於何時訪問根節點。

1. 前序遍歷 (Pre-Order Traversal)

順序： 根節點 \(\rightarrow\) 左子樹 \(\rightarrow\) 右子樹
運作方式： 先訪問根節點，接著遍歷整個左子樹，最後遍歷整個右子樹。
典型用途： 用於複製樹結構。如果你想重製這棵樹，首先必須知道根節點在哪裡！

2. 中序遍歷 (In-Order Traversal)

順序： 左子樹 \(\rightarrow\) 根節點 \(\rightarrow\) 右子樹
運作方式： 先遍歷左子樹，訪問根節點，最後遍歷右子樹。
典型用途： 如果對二元搜尋樹進行中序遍歷，輸出的內容會是升序排列（例如 1, 2, 3...）。

3. 後序遍歷 (Post-Order Traversal)

順序： 左子樹 \(\rightarrow\) 右子樹 \(\rightarrow\) 根節點
運作方式： 先訪問所有子節點，最後才訪問根節點。
典型用途： 用於刪除樹（在刪除子節點之前，你無法刪除父節點！）或將算式轉換為逆波蘭表示法 (Reverse Polish Notation, RPN)。

如果覺得這部分很難，別擔心！ 考試時有一個簡單的「輪廓技巧」。想像在樹的外圍畫一條緊密的線（輪廓），從根節點的左側開始。如果你在每個節點的左側標記一個點，按順序連接起來就是前序遍歷 (Pre-Order)；標記在下方是中序遍歷 (In-Order)；標記在右側則是後序遍歷 (Post-Order)。

重點總結： 遍歷只是穿過樹的不同「路徑」。前序用於複製，中序用於排序，後序則用於 RPN 或清空樹。


4. 關鍵概念總結

在繼續往下學習之前，請確保你已經掌握這些「必備知識點」：

  • 樹的定義： 連通、無向且無環的圖。
  • 有根樹： 擁有一個核心（根節點）的樹。
  • 二元樹： 每個節點最多只有 2 個子節點的樹。
  • 搜尋複雜度： 搜尋二元樹通常為 \(O(\log n)\)。
  • 遍歷順序： 記住這些順序！
    • 前序 (Pre-Order)：根、左、右
    • 中序 (In-Order)：左、根、右
    • 後序 (Post-Order)：左、右、根

避免常見錯誤： 不要假設每一棵樹都是二元樹！一般的樹在每個節點上可以有任意數量的子節點，只有「二元」樹才限制為兩個。

做得好！你剛剛已經掌握了數據結構中「樹」的基礎。繼續練習畫出這些遍歷路徑，你很快就會成為高手！