樹是一種連通且無環的圖。
指定一個頂點作為根（root）的樹，具有層次結構。
由多棵樹組成的圖（可以不連通）。
| 術語 | 英文 | 定義 | 例子 |
|---|---|---|---|
| 根 | Root | 樹的最上層頂點 | 上圖紅色頂點 |
| 內部頂點 | Internal Vertex | 有子節點的頂點 | 上圖藍色頂點 |
| 葉子 | Leaf / Leaves | 沒有子節點的頂點 | 上圖綠色頂點 |
| 子節點 | Children | 某頂點直接向下連接的頂點 | 一個頂點下方直接相連的點 |
| 父節點 | Parent | 某頂點直接向上連接的頂點 | 一個頂點上方直接相連的點 |
| 兄弟節點 | Siblings | 有相同父節點的頂點 | 同一個父節點的子節點們 |
| 祖先 | Ancestors | 從某頂點到根路徑上的所有頂點 | 往上追溯到根的所有點 |
| 後代 | Descendants | 某頂點下方的所有頂點 | 某點下方的所有子孫節點 |
每個內部頂點最多有m個子節點的有根樹。
每個內部頂點恰好有m個子節點的有根樹。
完滿m-元樹且所有葉子都在同一層。
邊數 = 頂點數 - 1
E = V - 1
問：一棵有10,000個頂點的樹有多少條邊？
答：10,000 - 1 = 9,999條邊
l = [(m-1)n + 1] / m
其中：l = 葉子數，n = 總頂點數，m = 每個內部頂點的子節點數
問：一棵有100個頂點的完滿3-元樹有多少個葉子？
答：l = [(3-1)×100 + 1] / 3 = [200 + 1] / 3 = 201 / 3 = 67個葉子
邊數 = 總頂點數 - 樹的數量
E = n - t
問：一個包含5棵樹、總共50個頂點的森林有多少條邊？
答：50 - 5 = 45條邊
葉子數 = 內部頂點數 + 1
l = i + 1
三個條件必須同時滿足！
從根到最遠葉子的路徑長度（邊數）。
頂點到根的距離。根在第0層。
| 題型 | 關鍵字 | 使用公式/方法 |
|---|---|---|
| 判斷是否為樹 | Which graphs are trees? | 檢查連通、無環、邊數=n-1 |
| 計算邊數 | How many edges? | E = V - 1 |
| 計算葉子數 | How many leaves? | l = [(m-1)n + 1]/m |
| 森林問題 | forest of t trees | 邊數 = n - t |
| 術語辨識 | parent, children, siblings等 | 根據定義判斷 |
記得：理解概念比死背公式更重要。遇到不會的題目先跳過，把會的題目做完再回來思考。