Learning Objectives
- 說明根、葉、子節點、父節點、子樹、深度、高度等術語，並在一棵樹上指出它們
- 用節點物件（val、left、right）建立二元樹
- 寫出前序、中序、後序走訪的遞迴程式，說明三者只差在「什麼時候處理自己」
- 用佇列寫出層序走訪，一層一層由左到右拜訪節點
- 用遞迴計算樹的高度與節點數，並能由前序與中序走訪結果反推出樹
有分支的資料
到目前為止的陣列、鏈結串列、堆疊、佇列都是線性的：每個元素前面最多一個、後面最多一個。很多資料不是這樣：
- 電腦的資料夾：一個資料夾裡有好幾個子資料夾，子資料夾裡還有子資料夾
- 運動比賽的賽程表：兩隊比完，勝者再和另一組的勝者比
- 算式
(3 + 4) * 5：*的兩邊各是一個小算式
這種「一個分成好幾個」的結構叫做樹（tree）。每個節點最多有兩個子節點的樹叫二元樹（binary tree），兩個子節點分別叫左子節點和右子節點。 二元樹是後面好幾課的基礎：第 14 課的二元搜尋樹、第 15 課的堆積都是二元樹。
樹的術語
這一課的範例都用這棵樹：
1
/ \
2 3
/ \ \
4 5 6
/
7
| 術語 | 意思 | 在這棵樹上 |
|---|---|---|
| 根（root） | 最上面的節點，沒有父節點 | 1 |
| 子節點（child）／父節點（parent） | 節點往下連到的節點是它的子節點；反過來是父節點 | 2、3 是 1 的子節點；5 是 7 的父節點 |
| 葉節點（leaf） | 沒有任何子節點的節點 | 4、7、6 |
| 子樹（subtree） | 某個節點和它底下所有節點組成的樹 | 以 2 為根的子樹是 2、4、5、7 |
| 深度（depth） | 從根往下走幾步才到這個節點；根的深度是 0 | 7 的深度是 3 |
| 高度（height） | 從根到最遠的葉節點，路徑上有幾個節點 | 整棵樹的高度是 4（1 → 2 → 5 → 7） |
高度有兩種算法：本課用「節點數」，空樹的高度是 0、只有根的樹是 1；有些書用「邊數」，結果會少 1。讀資料時先確認用的是哪一種。
節點的寫法和上一課的鏈結串列很像，只是 next 換成兩個欄位 left、right，沒有子節點時是 null（None、nullptr）。
建立一棵二元樹
先建立根，再一個一個接上子節點，樹就一層一層長出來。後半段用 node、leaf 兩個變數指到樹裡的節點，看它們的子節點。C++ 版本最後用 freeTree 釋放所有節點，它的順序會在後序走訪說明。
三種深度優先走訪
走訪（traversal）是把每個節點都拜訪一次。二元樹天生適合用遞迴處理：一棵樹＝根＋左子樹＋右子樹，左右子樹本身也是樹。 所以「走訪整棵樹」可以拆成「處理根」「走訪左子樹」「走訪右子樹」三件事，差別只在處理根的時機：
| 走訪 | 順序 | 這棵樹的結果 |
|---|---|---|
| 前序（preorder） | 自己 → 左子樹 → 右子樹 | 1, 2, 4, 5, 7, 3, 6 |
| 中序（inorder） | 左子樹 → 自己 → 右子樹 | 4, 2, 7, 5, 1, 3, 6 |
| 後序（postorder） | 左子樹 → 右子樹 → 自己 | 4, 7, 5, 2, 6, 3, 1 |
名稱裡的「前、中、後」指的就是「自己」排在第幾個。三種都是先一路往深處走，走到底才回頭，所以統稱深度優先走訪（depth-first traversal）。
遞迴的終止條件是空樹：節點是 null 就直接返回。每個節點恰好拜訪一次，時間 O(n)；遞迴呼叫堆疊的深度等於樹的高度。
前序走訪：先處理自己
每進入一個節點，第一件事就是把它的值放進 out，然後才往左、往右遞迴。看遞迴樹：每個真的節點都會呼叫兩次（左、右），走到 null 就立刻返回，所以 7 個節點共有 15 次呼叫。out 依序是 1, 2, 4, 5, 7, 3, 6。
中序與後序：同一個遞迴，換一行的位置
兩個函式的遞迴呼叫完全一樣，只有 out.append(node.val) 的位置不同。中序要等左子樹全部走完才處理自己，所以第一個輸出的是最左邊的 4；後序要等兩邊子樹都走完，所以根 1 最後才輸出。
三種走訪各有用途
- 前序：先處理父節點再處理子節點。複製一棵樹、把樹存成文字（序列化）、印出資料夾結構（先印資料夾名稱，再印裡面的東西）都用前序。
- 中序：在二元搜尋樹（下一課）上，中序走訪會由小到大輸出所有值。
- 後序：先處理子節點再處理父節點。要算出「這個資料夾總共多大」，得先知道每個子資料夾多大；
C++ 釋放整棵樹時也必須先刪子節點，最後才刪自己，否則刪掉父節點後就找不到子節點了。範例裡的
freeTree就是後序走訪。
算式樹也是個好例子：(3 + 4) * 5 的根是 *，左子樹是 3 + 4，右子樹是 5。
用後序走訪計算，就是「先算出兩邊的值，再做自己的運算」；把三種走訪的結果寫出來，分別是 * + 3 4 5、3 + 4 * 5、3 4 + 5 *（前序、中序、後序）。
想一想：三種走訪
下面的程式會印出什麼？
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorder(node, out):
if node is None:
return
inorder(node.left, out)
out.append(node.val)
inorder(node.right, out)
# 10
# / \
# 5 20
# / \
# 3 8
root = Node(10, Node(5, Node(3), Node(8)), Node(20))
out = []
inorder(root, out)
print(out)
同一棵樹（10 的左子節點 5、右子節點 20；5 的左右子節點是 3 和 8），後序走訪的結果是什麼？
要用 C++ 的 delete 釋放整棵樹的所有節點，應該用哪一種走訪的順序？
層序走訪：一層一層來
層序走訪（level-order traversal）先拜訪第 0 層（根），再由左到右拜訪第 1 層、第 2 層……這棵樹的結果是 1, 2, 3, 4, 5, 6, 7。
遞迴會一路往深處走，不適合「一層一層」的順序。這裡要用第 10 課的佇列（先進先出）：
- 把根放進佇列
- 從佇列前面取出一個節點，處理它
- 把它的左、右子節點（不是 null 的）放到佇列後面
- 佇列還有東西就回到第 2 步
子節點排在佇列後面，要等同一層、排在前面的節點都處理完才會輪到它們，所以輸出的順序剛好是一層一層。 每個節點進出佇列各一次，時間 O(n)。第 16 課的廣度優先搜尋（BFS）是同一個想法用在圖上。
層序走訪：佇列裡的節點
看佇列的變化（右下角的變數區可以看到 q 裡的節點）：取出 1，放進 2、3；取出 2，放進 4、5；取出 3，放進 6……輸出的順序就是一層一層、由左到右。（C++ 用 queue，取出要先 front() 再 pop()；Java 用 ArrayDeque 的 add、poll；函式名稱是 levelOrder。）
用遞迴算高度與節點數
很多樹的問題都能寫成「把左右子樹的答案組合起來」：
- 高度：空樹是 0；否則是 1（自己這一層）加上左右子樹高度比較大的那一個
- 節點數：空樹是 0；否則是 1（自己）加上左子樹的節點數、再加上右子樹的節點數
def height(node):
if node is None:
return 0
return 1 + max(height(node.left), height(node.right))
這其實是後序走訪：要先知道兩個子樹的答案，才能算出自己的答案。兩個函式都把每個節點拜訪一次，O(n)。
高度與節點數
看遞迴樹上的回傳值：葉節點的兩個子樹都是 null（回傳 0），所以葉節點回傳 1；往上一層取兩邊比較大的再加 1。節點 5 的左邊高度 1、右邊 0，回傳 2；節點 2 的兩邊是 1 和 2，回傳 3；根回傳 4。（C++、Java 的節點數函式叫 countNodes。）
從走訪結果反推樹
只給一種走訪結果，通常無法確定樹長什麼樣子。例如前序 1, 2 可能是「2 是 1 的左子節點」，也可能是「2 是 1 的右子節點」。
但如果同時知道前序和中序（而且節點的值都不相同），樹就唯一確定：
- 前序的第一個一定是根
- 在中序裡找到根：根左邊的都在左子樹，右邊的都在右子樹
- 依左子樹的節點數，把前序也切成左右兩段，對兩邊重複同樣的步驟
用本課的樹驗證：前序 1, 2, 4, 5, 7, 3, 6、中序 4, 2, 7, 5, 1, 3, 6。
- 根是 1；中序裡 1 的左邊
4, 2, 7, 5是左子樹（4 個節點），右邊3, 6是右子樹 - 前序去掉根之後，前 4 個
2, 4, 5, 7是左子樹的前序，後面3, 6是右子樹的前序 - 左子樹的根是 2；中序
4, 2, 7, 5裡，2 的左邊是 4、右邊是7, 5……一路切下去，就得到原本的樹
後序加中序也可以（後序的最後一個是根）；但前序加後序在某些情況下無法區分左右，例如上面的 1, 2。
想一想：層序、高度與反推
對本課的樹（1 的子節點 2、3；2 的子節點 4、5；3 的右子節點 6；5 的左子節點 7）做層序走訪。剛把節點 2 從佇列取出、並放進它的子節點之後，佇列裡依序是哪些節點？
一棵二元樹的前序是 A, B, D, E, C，中序是 D, B, E, A, C。根的左子樹有哪些節點？
一棵有 7 個節點的二元樹，用本課的定義（節點數），高度最小和最大分別是多少？
實作：葉節點個數與節點值總和
請用遞迴完成兩個函式：count_leaves 算葉節點的個數，tree_sum 算所有節點的值加起來是多少（C++、Java 是 countLeaves、treeSum）。兩個都是「空樹回傳 0，否則組合左右子樹的答案」。
重點整理
- 二元樹的每個節點有
val、left、right；沒有父節點的是根，沒有子節點的是葉節點 - 深度：根是 0，往下一層加 1；高度（本課的定義）：根到最遠葉節點路徑上的節點數，空樹是 0
- 前序：自己 → 左 → 右；中序：左 → 自己 → 右；後序：左 → 右 → 自己；三種都是遞迴，O(n)
- 層序：用佇列，取出一個節點、把子節點放到後面，一層一層由左到右
- 高度、節點數等問題寫成「空樹回傳 0，否則組合左右子樹的答案」
- 前序（或後序）加上中序，就能唯一反推出一棵值都不相同的二元樹
下一課：二元搜尋樹。在二元樹上加一條規則「左邊都比較小、右邊都比較大」，搜尋就能像二分搜尋一樣，每一步排除一半。