前序、中序、後序的非遞迴遍歷中,要數後序最為麻煩。原因是後序必須在左右子樹都處理完之後才拜訪根節點,而只在堆疊中保留指向節點的指標並不足夠,必須有一些額外資訊存放在堆疊裡。
方法有很多,這裡只舉一種:先定義堆疊節點的資料結構。
typedef struct {
Node *p;
int rvisited; // ==1 代表 p 所指向的節點的右節點已被訪問過
} SNode; // Node 是二叉樹的節點結構
lastOrderTraverse(BiTree bt) {
// 首先,從根節點開始往左下方走,一直走到頭,
// 將路徑上的每一個節點入堆疊
p = bt;
while (bt) {
push(bt, 0); // 入堆疊兩個資訊:節點指標、右節點是否被訪問過
bt = bt.lchild;
}
// 然後進入循環體
while (!Stack.empty()) {
sn = Stack.getTop(); // sn 是堆疊頂節點
// 注意:任意一個節點 N,只要它有左孩子,則 N 入堆疊之後,
// N 的左孩子必然也跟著入堆疊了(這體現在演算法的後半部分)。
// 所以當我們拿到堆疊頂元素的時候,可以確信這個元素要麼沒有左孩子,
// 要麼其左孩子已經被訪問過 —— 此時就不關心它的左孩子,只關心右孩子。
// 若其右孩子已被訪問過,或該元素沒有右孩子,
// 則由後序遍歷的定義,此時可以 visit 這個節點了
if (!sn.p.rchild || sn.rvisited) {
p = pop();
visit(p);
} else {
// 若它的右孩子存在且 rvisited 為 0,說明以前還沒有動過它的右孩子,
// 於是就去處理一下其右孩子。
// 此時要從其右孩子節點開始一直往左下方走,直至走到盡頭,
// 將這條路徑上的所有節點都入堆疊。
// 當然,入堆疊之前要先將該節點的 rvisited 設成 1,
// 因為其右孩子的入堆疊意味著它的右孩子必將先於它被訪問
//(因為我們總是從堆疊頂取出元素來 visit)。
// 由此可知,下一次該元素再處於堆疊頂時,
// 其右孩子必然已被 visit 過了。
sn.rvisited = 1;
p = sn.p.rchild;
while (p != 0) {
push(p, 0);
p = p.lchild;
}
}
// 這一輪循環已結束,剛剛入堆疊的那些節點不必管,
// 下一輪循環會把這些節點照顧得很好
}
}
關鍵在於一個不變式:「左孩子一定比父節點晚被拜訪、右孩子也一定比父節點晚被拜訪」,這是由「先一路向左下壓堆疊」的動作保證的。rvisited 只是把「右子樹是否已完成」這個狀態保存在堆疊裡,彌補了單一指標無法表達的資訊。
另一種常見做法是使用 prev 指標:記住上一個拜訪過的節點,若目前堆疊頂的右孩子等於 prev,或(沒有右孩子且)左孩子等於 prev,就可以出堆疊並拜訪。這種寫法不必修改節點結構,實作上往往更清爽,值得一併比較。