Learning Objectives
- 說出根、葉、深度、高度、度數的意思，並在一棵樹上算出來
- 用「子節點串列」與「左子右兄弟」兩種方式表示一般樹，並把一般樹轉成二元樹
- 用陣列表示二元樹：算出第 i 格的父節點與左右子節點，說明這種表示法什麼時候浪費空間
- 寫出前序、中序、後序的遞迴走訪，並從運算式樹讀出前序式、中序式、後序式
- 用自己管理的堆疊寫出不遞迴的中序走訪，用佇列寫出一層一層的層序走訪
- 由前序與中序重建出唯一的二元樹
有分支的結構
前面幾課的陣列、串列、堆疊、佇列都是線性的：每個元素前後最多各一個。樹（tree）讓一個節點可以有好幾個後繼：
- 檔案系統：資料夾裡有資料夾
- 公司或學校的組織圖
- 運算式
(A + B) * (C - D) / E：每個運算子的兩邊各是一個小運算式
這一課從資料結構的角度看樹：節點裡要存什麼、指標怎麼接、走訪時用什麼結構記住「還沒處理的部分」。 二元樹的三種遞迴走訪在演算法軌第 13 課看過一次；這一課換一棵運算式樹，並加上陣列表示法、不遞迴的寫法與重建。
術語（以下用這棵一般樹）：
A 深度 0
/ | \
B C D 深度 1
/ \ \
E F G 深度 2
\
H 深度 3
| 術語 | 意思 | 在這棵樹上 |
|---|---|---|
| 根（root） | 唯一沒有父節點的節點 | A |
| 葉（leaf） | 沒有子節點的節點 | E、F、C、H |
| 度數（degree） | 一個節點有幾個子節點；樹的度數是所有節點度數的最大值 | A 的度數 3、D 的度數 1；這棵樹的度數是 3 |
| 深度（depth） | 從根走到這個節點要幾步，根是 0 | H 的深度 3 |
| 高度（height） | 從根到最遠的葉，路徑上有幾層 | 4（A → D → G → H） |
| 兄弟（sibling） | 父節點相同的節點 | B、C、D 互為兄弟 |
高度有兩種算法：本課數「層數」（只有根的樹高度是 1），有些書數「邊數」（只有根的樹高度是 0），讀資料時先確認。
一般樹：每個節點一個子節點串列
子節點的個數不固定時，最直接的寫法是每個節點存一個子節點串列：Python 的 list、C++ 的 vector<Node*>、Java 的 ArrayList<Node>。show 先印自己再依序印每一棵子樹，縮排的格數就是深度；len(children) 就是度數。height 取最高的子樹再加 1，所以要等所有子樹都算完才知道自己的高度。
左子右兄弟：用二元樹表示一般樹
子節點串列很直覺，但每個節點的大小不固定。如果規定每個節點都留 k 個指標（k 是樹的度數），大部分指標會是空的： n 個節點的 k 元樹共有 n × k 個指標，真正用到的只有 n - 1 個（除了根，每個節點剛好被一個指標指到）。
左子右兄弟（left-child right-sibling）表示法讓每個節點固定只有兩個指標：
left指向第一個子節點right指向下一個兄弟
一般樹 左子右兄弟（left 往左下、right 往右）
A A
/ | \ /
B C D B ──→ C ──→ D
/ \ \ / /
E F G E ──→ F G
\ /
H H
要找某個節點的所有子節點：先沿 left 走一步，再一路沿 right 走到底。
轉換後的結構就是一棵二元樹，所以二元樹的演算法和程式碼都能拿來處理一般樹。
把一般樹轉成左子右兄弟的二元樹
convert 是遞迴：先把每個子節點轉好（cb），第一個掛在自己的 left，之後的接在前一個兄弟（prev）的 right。轉完之後看第二個面板：A 只有 left（B），B、C、D 沿著 right 排成一列；H 是 G 的 left，因為 H 是 G 唯一的子節點。最後用「先往左一步、再一路往右」印出 A 和 B 的子節點。
二元樹的兩種表示法
節點表示：每個節點存 val、left、right，沒有子節點時是 null。插入、刪除都只要改指標，樹長什麼樣子都可以。
陣列表示：把節點依「一層一層、由左到右」的順序放進陣列，根在第 0 格。第 i 格的節點：
| 要找 | 位置 |
|---|---|
| 左子節點 | 2i + 1 |
| 右子節點 | 2i + 2 |
| 父節點 | (i - 1) / 2（整數除法） |
不用存任何指標，位置用算的。代價是缺少的節點也要留空位。這一課用運算式 (A + B) * (C - D) / E 的樹：
/ 索引 0 1 2 3 4 5 6 7 8 9 10
/ \ / * E + - . . A B C D
* E
/ \ E（第 2 格）沒有子節點，第 5、6 格留空（.）
+ -
/ \ / \
A B C D
樹很「滿」的時候（例如第 14 課的堆積是完全二元樹，中間沒有空位），陣列表示最省； 樹很歪的時候很浪費：一條往右長、高度 h 的鏈只有 h 個節點，卻要 2ʰ - 1 格。
下面用陣列表示法寫三種遞迴走訪：遞迴參數是索引 i，不是節點指標；「超出陣列或是空位」就當成空樹。
陣列表示的前序、中序、後序
三個函數只差在「把自己放進 out」那一行的位置：在兩個遞迴呼叫之前是前序、中間是中序、之後是後序。運算式樹的三種走訪剛好是三種寫法：前序 / * + A B - C D E 是前序式（波蘭表示法），中序 A + B * C - D / E 是平常的寫法但少了括號，後序 A B + C D - * E / 是後序式（第 05 課用堆疊求值的那一種）。
想一想：術語與表示法
本課開頭的一般樹（A 有子節點 B、C、D；B 有 E、F；D 有 G；G 有 H），下列哪一組正確？
用陣列表示二元樹（根在第 0 格）。第 4 格節點的父節點、左子節點、右子節點分別在第幾格？
把本課的一般樹轉成左子右兄弟的二元樹之後，B 節點的 left 和 right 分別指向誰？
不用遞迴：自己管理堆疊
遞迴走訪之所以能「走完左子樹再回來處理自己」，是因為呼叫堆疊記住了每一層還沒做完的事。 樹很深的時候（例如退化成一條長鏈），遞迴可能超過語言的遞迴深度上限；這時可以自己用一個堆疊記住那些還沒輸出的祖先。
中序走訪的做法：
- 從
cur = root開始，一路往左走，經過的節點都推進堆疊（它們的左子樹還沒走完，暫時不能輸出） - 走到 null 了：彈出堆疊頂端的節點，它的左子樹已經走完，輸出它
- 換到它的右子樹（
cur = cur.right），回到第 1 步 cur是 null 而且堆疊也空了，才全部結束
堆疊裡最多同時放「從根到目前節點的那一條路徑」，所以額外空間是 O(樹高)；每個節點進出堆疊各一次，時間 O(n)。 三種語言都用可以從尾端加入與移除的動態陣列當堆疊（Python list、C++ vector、Java ArrayList），堆疊頂端在最右邊。
用堆疊寫中序走訪
一開始一路往左：/、*、+、A 依序進堆疊。A 沒有左子節點，彈出 A 輸出，再走 A 的右子樹（null），所以接著彈出 +。注意堆疊的長度：最多同時放 4 個節點，剛好是樹高。
層序走訪：一次處理一整層
層序走訪（level order）依深度一層一層、同一層由左到右拜訪。和深度優先的三種走訪不同，它要的是「先發現的先處理」，所以用佇列：
- 根放進佇列
- 佇列不空時：取出最前面的節點，拜訪它，再把它的左、右子節點（不是 null 的）放到佇列後面
要分層印出時多一個技巧：每一輪開始時，佇列裡剛好是同一層的所有節點，先記下個數 n，這一輪只取出 n 個。取出時放進去的子節點屬於下一層，下一輪才處理。
| 語言 | 佇列 | 放到後面 | 從前面取出 |
|---|---|---|---|
| Python | collections.deque |
append |
popleft |
| C++ | queue<Node*> |
push |
front 再 pop |
| Java | ArrayDeque<Node> |
offer |
poll |
陣列表示的二元樹不需要佇列：陣列本來就是依層序存放，從第 0 格往後掃一遍、跳過空位，就是層序走訪。
用佇列一層一層印出
每一輪開始時看佇列：第 0 輪只有 /，第 1 輪是 * E，第 2 輪是 + -，第 3 輪是 A B C D。每一輪取出 n 個節點，同時把它們的子節點排到後面；印出的四行就是樹的四層。
由前序與中序重建二元樹
只給一種走訪結果，通常有很多棵樹符合。但前序＋中序（節點的值都不相同時）可以唯一決定一棵二元樹：
- 前序的第一個是根
- 在中序裡找到根：根的左邊全部是左子樹，右邊全部是右子樹
- 左子樹有幾個節點（設為 L），前序在根之後的前 L 個就是左子樹的前序，其餘是右子樹的前序
- 對左、右兩段重複同樣的步驟，直到某一段是空的
用本課的運算式樹驗證：前序 / * + A B - C D E、中序 A + B * C - D / E。根是 /；中序裡它的左邊有 7 個（A + B * C - D），右邊只有 E；
前序在 / 之後的 7 個 * + A B - C D 是左子樹的前序……一路切下去。
後序＋中序也可以（後序的最後一個是根）。前序＋後序不一定可以：只有一個子節點時分不出左右，例如前序 A B、後序 B A，B 可能是 A 的左子節點，也可能是右子節點。
下面的實驗室可以一步一步練習重建：每一步在中序的範圍裡點出根的位置，程式把兩個序列切開。
想一想：走訪與重建
下面的程式會印出什麼？（運算式 (A - B) * C 的樹）
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def post(n, out):
if n is None:
return
post(n.left, out)
post(n.right, out)
out.append(n.val)
root = Node("*", Node("-", Node("A"), Node("B")), Node("C"))
out = []
post(root, out)
print(" ".join(out))
用堆疊做本課運算式樹的中序走訪。第一次輸出 A 之後，堆疊裡從底到頂是哪些節點？
一棵二元樹的前序是 A B D E C F、中序是 D B E A C F。它的後序是什麼？
實作：由前序與中序重建
請完成 build(pre, ino, pl, il, ir)：這棵子樹的前序從 pre[pl] 開始，中序是 ino[il..ir]，回傳重建好的子樹的根。程式會對兩組資料各重建一次，印出後序來驗證。可以切換成你熟悉的語言。
重點整理
- 術語：根、葉、度數（子節點個數；樹的度數取最大值）、深度（根是 0）、高度（本課數層數）、兄弟
- 一般樹的兩種表示：子節點串列（直覺、節點大小不固定）；左子右兄弟（每個節點固定兩個指標，轉成二元樹）
- 二元樹的兩種表示：節點加指標（任何形狀都可以）；陣列（第 i 格的子節點在 2i+1、2i+2，父節點在 (i-1)/2；樹很歪時浪費空間）
- 前序、中序、後序只差在「處理自己」放在兩個遞迴呼叫的前、中、後；運算式樹的三種走訪就是前序式、中序式（少括號）、後序式
- 不遞迴的中序：一路往左推進堆疊，走到底就彈出、輸出、轉向右子樹；空間 O(樹高)
- 層序用佇列；每一輪先記下佇列的長度，就能一層一層印出
- 前序＋中序（或後序＋中序）可以唯一重建二元樹；前序＋後序不一定可以
下一課：二元搜尋樹的插入與刪除。中序走訪會派上用場：二元搜尋樹的中序就是由小到大。