前序、中序、後序三種深度優先遍歷中,後序是最麻煩的一個。原因是後序要求「左 → 右 → 根」,而當我們沿著左路徑往下走時,必須記得「回頭還要處理右子樹」。若只在堆疊裡放節點指標,資訊是不够的——必須額外記錄每個節點的右子樹是否已拜訪過。
typedef struct {
Node *p;
int rvisited; // ==1 代表 p 所指節點的右子節點已被拜訪過
} SNode;
void lastOrderTraverse(BiTree bt) {
// 第一步:從根節點出發一路向左下走到底,路徑上每個節點入堆疊
Node *p = bt;
while (p) {
push(p, 0); // 入堆疊:節點指標 + 右子節點是否已拜訪(0)
p = p->lchild;
}
// 第二步:進入主迴圈
while (!Stack.empty()) {
SNode sn = Stack.getTop(); // 取堆疊頂端元素
// 注意:任一枚舉 N,只要它有左孩子,N 入堆疊後左孩子必然也入堆疊了。
// 所以拿到堆疊頂時可以確定:這個元素要嘛沒有左孩子,
// 要嘛左孩子已經被拜訪過 —— 因此不必再管左孩子,只關心右孩子。
// 情況一:沒有右孩子,或右孩子已拜訪過 → 可以拜訪它了
if (!sn.p->rchild || sn.rvisited) {
pop();
visit(sn.p);
}
// 情況二:右孩子存在且未拜訪 → 先處理右子樹
else {
sn.rvisited = 1; // 標記:右孩子即將入堆疊,意味著它會先被拜訪
// 從右孩子開始一路向左下走到底,路徑上全部入堆疊
p = sn.p->rchild;
while (p != 0) {
push(p, 0);
p = p->lchild;
}
// 這一輪剛入堆疊的節點不必理會,下一輪迴圈會照顧好它們
}
}
}
關鍵在兩個不變式:
這兩個性質合起來,正好對應後序遍歷「左右根」的定義。相比遞迴版本,這個寫法用一個整數旗標換掉了系統呼叫堆疊,在深度很大或需要自行管理堆疊的環境中特別有用。