樹的走訪不只是一組要背誦的名詞。走訪把分支結構化成一條線性序列；重建則反過來追問：序列究竟保留了多少原有結構？兩件事都由同一個遞迴分解支配，也就是根節點、左子樹、右子樹。
本節先精確定義三種深度優先走訪，再證明遞迴程序正確，最後研究如何由前序加中序，或後序加中序重建二元樹。所有「唯一重建」結論都有一個不可省略的前提：各節點的鍵值互不相同。
動機
假設程式走訪一棵樹後，只保存節點鍵值的序列。另一個程式日後能否恢復完全相同的樹？答案取決於走訪次序顯露了甚麼。
- 前序走訪會在後代之前顯露每棵非空子樹的根節點。
- 後序走訪會在後代之後顯露該根節點。
- 中序走訪把整棵左子樹放在根節點之前，把整棵右子樹放在根節點之後。
其中任何一項通常都不足以獨立還原結構。有效的配搭是：前序或後序負責指出根節點，中序負責指出左右子樹的分界。因此，重建不是一套零散技巧，而是重複維持同一個遞迴不變量。
定義
定義
二元樹與遞迴子樹結構
二元樹要麼是空樹，要麼由一個根節點及一對有次序的二元樹組成；兩者分別稱為左子樹與右子樹，任何一邊都可以是空樹。
左右次序是結構的一部分。交換左、右子節點後，一般會得到另一棵二元樹。
非空樹的根節點沒有父節點。直接位於某節點下一層的是其子節點；沿子節點連結反覆向下可到達的節點是後代，反方向則是祖先。沒有子節點的是葉節點，至少有一個子節點的是內部節點。以某節點為根的子樹，包含該節點及其全部後代。
以下以 h 表示最長根至葉路徑上的節點數，因此單節點樹的高度為 1。這項約定令稍後的遞迴堆疊界線沒有歧義。
定義
前序、中序與後序走訪
對根節點為 R、左子樹為 L、右子樹為 T 的非空二元樹：
- 前序（preorder）是
R，再走訪L，最後走訪T； - 中序（inorder）是先走訪
L，再到R，最後走訪T； - 後序（postorder）是先走訪
L，再走訪T，最後才到R。
空樹的走訪結果是空序列。
定義可直接寫成遞迴偽代碼：
Preorder(node): Inorder(node):
if node is null: return if node is null: return
visit(node) Inorder(node.left)
Preorder(node.left) visit(node)
Preorder(node.right) Inorder(node.right)
Postorder(node):
if node is null: return
Postorder(node.left)
Postorder(node.right)
visit(node)
三個程序只改變 visit 的位置，卻會改變每段子樹序列的開端或末端所顯示的資訊。中序走訪本身不是排序；只有當樹另行滿足二元搜尋樹的不變量時，中序鍵值才會遞增。該不變量會在下一篇筆記處理。
還要精確分辨各序列保留的資料。在邊界已知的子樹內，前序首項是根，後序末項是根；若根已知，中序中根之前的項全部屬左子樹，之後的項全部屬右子樹。可是中序本身不會指出哪一項是根，而本節採用的三種序列也不記錄空子節點標記。這正好解釋重建定理的兩面：可辨認根的次序與中序互相補足；欠缺分界或根的選擇時，多種樹形便可能共用同一序列。
「邊界已知」尤其重要。只有在遞迴演算法已確立區間後，一段連續走訪序列才代表一棵子樹；不能任意從完整序列截取一段，便假設它必然是一棵子樹。
定理 / 命題
定理
遞迴走訪不變量
三種程序中的任何一個在某棵子樹上執行時，都會恰好一次走訪該子樹的每個節點，不會走訪子樹以外的節點，並按照相應遞迴定義輸出節點。
定理
由中序及可辨認根節點的次序唯一重建
假設所有節點鍵值互異。若兩個相容序列分別是一棵二元樹的前序和中序走訪，它們唯一決定一棵有左右次序的二元樹。後序配合中序亦有相同結論。
定理
單一中序序列並不足夠
即使鍵值互異，單憑中序走訪一般也不能決定根節點、父子關係或二元樹形狀。
「相容」並非多餘字眼。兩個輸入必須長度相同、鍵值集合相同，而且每次遞迴選出的根都必須位於當前中序區間內；否則兩個序列並不描述同一棵樹。
證明思路
走訪正確性可對子樹節點數作歸納。空樹呼叫立即返回，命題成立。對非空子樹，兩次遞迴呼叫分別作用於更小的左、右子樹，因此依歸納假設已正確。程序只走訪根一次，並把它放在兩段正確結果之前、之間或之後，所以每個節點恰好出現一次，次序也符合定義。
考慮由前序和中序重建，令 P、I 表示當前兩段序列。P 的第一個鍵必為根 r。由於鍵值互異，r 在 I 只有一個位置；其前方全部屬左子樹，後方全部屬右子樹。兩邊長度因而把 P 的餘下部分唯一切成左右兩段。對兩段重複同一論證，以長度作歸納便同時得到相容輸入的存在性和唯一性。
若用後序，當前後序段最後一個鍵就是根。中序仍然固定左右大小，而後序段的形式是「左、右、根」，所以兩段子樹輸入亦被唯一決定。
鍵值互異不是裝飾性條件。若有重複值，根值可能在中序出現數次，「在中序找根」便不能選出唯一分界。此時必須加入節點身分，例如為每次出現加獨立標籤，或清楚規定重複值政策；原始重複值本身不足以套用上述定理。
以下反例證明單一中序不足。兩棵樹的中序同為 (B, A, C)：
A C
/ \ /
B C A
/
B
序列只固定由左至右的次序，沒有指出哪個鍵是根。同樣地，前序 (A, B) 和後序 (B, A) 既可以描述 B 是左子節點，也可以描述它是右子節點。因此，若沒有額外結構條件，前序加後序仍不足以唯一重建任意二元樹。
例題
例題
在同一棵樹追蹤三種次序
考慮課程走訪例子中的樹：
A
/ \
B C
/ / \
D E F
\ / \
G H J
在每棵子樹分別套用遞迴規則，可得：
- 前序：
A, B, D, C, E, G, F, H, J； - 中序：
D, B, A, E, G, C, H, F, J； - 後序：
D, B, G, E, H, J, F, C, A。
例如以 C 為根的子樹，在三種次序中分別貢獻 C,E,G,F,H,J、E,G,C,H,F,J 和 G,E,H,J,F,C。先把它視為較小的完整問題，可避免把節點誤放到相鄰子樹。
例題
由前序與中序重建
使用上述前序與中序。前序首項是 A，所以根為 A。中序可寫成
D,B | A | E,G,C,H,F,J，
左子樹有兩個節點，故前序中緊接 A 的 B,D 構成左子樹，餘下 C,E,G,F,H,J 構成右子樹。
左段以 B 為根，而 D | B 表示 D 是其左子節點。右段以 C 為根，E,G | C | H,F,J 固定一棵兩節點左子樹和一棵三節點右子樹。繼續分割，得到 E 的右子節點 G，以及 F 的左、右子節點 H、J。
使用閉區間索引及「鍵值至中序位置」索引表，核心程序如下：
BuildPre(preLo, preHi, inLo, inHi):
if preLo > preHi or inLo > inHi:
require preLo > preHi and inLo > inHi
return null
rootKey = preorder[preLo]
k = inorderPosition[rootKey]
require inLo <= k <= inHi
leftSize = k - inLo
node = new Node(rootKey)
node.left = BuildPre(preLo + 1, preLo + leftSize,
inLo, k - 1)
node.right = BuildPre(preLo + leftSize + 1, preHi,
k + 1, inHi)
return node
例題
由後序與中序重建
改用後序 D,B,G,E,H,J,F,C,A 及同一中序。後序末項 A 是根；中序仍給出左邊兩個、右邊六個節點，因此後序分成
D,B | G,E,H,J,F,C | A。
右段末項是 C；其中序分割為 E,G | C | H,F,J，所以對應後序子段為 G,E 和 H,J,F。由此得到 E 的右子節點 G，以及 F 的兩個子節點 H、J。
BuildPost(postLo, postHi, inLo, inHi):
if postLo > postHi or inLo > inHi:
require postLo > postHi and inLo > inHi
return null
rootKey = postorder[postHi]
k = inorderPosition[rootKey]
require inLo <= k <= inHi
leftSize = k - inLo
node = new Node(rootKey)
node.left = BuildPost(postLo, postLo + leftSize - 1,
inLo, k - 1)
node.right = BuildPost(postLo + leftSize, postHi - 1,
k + 1, inHi)
return node
這個區間版本先建哪一邊都可以。若另一種實作以同一游標從後序末端逐項讀取，就必須先建右子樹，因為反向讀取的次序是「根、右、左」。
例題
先辨認不相容輸入，不要虛構樹
若前序是 (A, B, C)，中序卻是 (B, A, D)，兩者鍵值集合不同，所以不存在同時具有這兩個走訪結果的樹。另一種錯誤是：當前前序根雖在完整中序出現，卻落在當前中序區間之外；這表示它與較早的父子分割矛盾。穩健的實作應拒絕輸入，而不是靜默傳回殘缺的樹。
複雜度
假設 visit 只做常數時間的局部工作，每種走訪都恰好處理 n 個節點一次，故時間為 Theta(n)。遞迴呼叫堆疊佔 O(h) 空間：當樹高對 n 是對數級時為 O(log n)，完全偏斜的樹則為 O(n)。若要保存輸出序列，另需 Theta(n) 空間。
重建時若每次都線性掃描當前中序段找根，偏斜輸入可令總時間達 Theta(n^2)。較好的方法是先檢查鍵值集合，以 Theta(n) 時間建立每個互異鍵值至中序索引的表，並傳遞索引界線而非複製子陣列。假設查表為常數時間，每個節點只建立一次，總時間便是 Theta(n)。索引表佔 Theta(n) 輔助空間，遞迴另佔 O(h)；輸出的樹本身必然佔 Theta(n)。
常見錯誤
常見錯誤
以為任何二元樹的中序都有排序效果
中序只代表「左、根、右」。只有另一項不變量，例如二元搜尋樹不變量，才保證鍵值遞增。
常見錯誤
用前序或後序猜左右分界
前序、後序能指出子樹根；左右各有多少節點，則須由中序決定。缺少這個分界時，子樹邊界一般有歧義。
常見錯誤
忘記鍵值互異的前提
同一值出現多次時，單一「值至索引」表不能證明根只有一個位置；必須標記每次出現或另定重複值政策。
常見錯誤
把平方時間藏在遞迴內
每層掃描中序或複製切片，都可能令看似簡單的程序變成平方時間。應預先建立位置表並傳遞界線。
常見錯誤
反向游標先建立錯誤的一邊
用共享游標由後序末端讀取時，應先右後左。區間版本已明確計算兩段，沒有這項先後依賴。
總結
- 三種走訪只改變根節點的處理時刻，卻各自顯露不同結構資訊。
- 每次遞迴呼叫只負責一棵子樹，這正是走訪正確性的不變量。
- 鍵值互異時，前序加中序或後序加中序可唯一決定有左右次序的二元樹。
- 單憑中序，以及對任意二元樹只用前序加後序，都可能有歧義。
- 位置索引表加區間界線，可把可能的
Theta(n^2)重建降至Theta(n)。
練習
思考檢查
1. 一棵樹以 M 為根；左子節點 H 有右子節點 K；右子節點 T 有左子節點 P。寫出前序、中序與後序。
先在每棵子樹套用同一遞迴模板，再合併結果。
思考檢查
2. 已知前序為 (M,H,K,T,P)，中序為 (H,K,M,P,T)，找出根及兩棵子樹各自的兩段序列。
利用根在中序的位置及由此得到的左子樹大小。
思考檢查
3. 已知後序為 (K,H,P,T,M)，中序同上，找出根及左右後序子段。
根在後序末端，而中序仍提供兩邊大小。
思考檢查
4. 解釋前序 (A,B) 與後序 (B,A) 為何不能判斷 B 是左子節點還是右子節點。
構造兩棵具有相同序列的有序二元樹。
思考檢查
5. 為何每層掃描中序可能需要平方時間？哪兩項實作選擇可恢復線性時間？
先考慮偏斜樹，再分開處理找根與複製子陣列的成本。
解答
解答 · 1. 走訪追蹤
前序為 M,H,K,T,P；中序為 H,K,M,P,T；後序為 K,H,P,T,M。對 H 而言，空左子樹沒有輸出；K 在前序緊接 H，但在另兩種走訪中要先完成相應子樹才返回 M。
解答 · 2. 前序與中序分割
根是 M。中序分為 H,K | M | P,T，左右各兩個節點；讀取前序的根項 M 後，餘下前序段相應分為 H,K | T,P。兩組遞迴輸入分別是前序 (H,K) 配中序 (H,K)，以及前序 (T,P) 配中序 (P,T)。
解答 · 3. 後序與中序分割
末項 M 是根。由中序大小可把之前的後序鍵分成 K,H | P,T | M。因此左後序 (K,H) 配左中序 (H,K)；右後序 (P,T) 配右中序 (P,T)。
解答 · 4. 歧義
第一棵樹以 A 為根、B 為左子節點；第二棵以 A 為根、B 為右子節點。兩者前序都是先 A 後 B，後序都是先 B 後 A。序列沒有記錄哪一邊為空，所以不能分辨形狀。
解答 · 5. 修正複雜度
偏斜樹上的掃描長度可依次為 n,n-1,...,1，總和是 Theta(n^2)。先建立「鍵值至中序索引」表，令每次找根為常數時間；再傳遞整數界線，避免複製子陣列。於查表假設下，每個節點只處理一次，總時間為 Theta(n)。