先序遍歷用遞迴寫只要三行,但一旦要改成非遞迴版本,就必須自己維護狀態,而狀態就得靠堆疊。本文記錄了以堆疊實作先序遍歷的三個版本,以及前兩版為什麼會出錯。
先序(先根)遍歷的非遞迴思路可以拆成四步:
int PreOrderTraverseNonRecursiveEx(const BiTree &T, int (*VisitNode)(TElemType data)) {
if (T == NULL) { return -1; }
BiTNode *pBiNode = T;
SqStack S;
InitStack(&S);
Push(&S, (SElemType)T);
while (!IsStackEmpty(S)) {
while (pBiNode) {
VisitNode(pBiNode->data);
if (pBiNode != T) {
Push(&S, (SElemType)pBiNode);
}
pBiNode = pBiNode->lchild;
}
if (pBiNode == NULL) {
Pop(&S, (SElemType*)&pBiNode);
}
if (pBiNode->rchild == NULL) {
Pop(&S, (SElemType*)&pBiNode); // 此時堆疊可能已空
}
pBiNode = pBiNode->rchild;
}
return 0;
}
這裡有個容易忽略的細節:入堆疊時存的是指標位址,並以 int 型別保存;因此出堆疊時傳的是 &pBiNode 而不是 pBiNode。若把宣告改成 BiTree pBiNode 會更好理解。
但這個版本本身是錯的。除錯過程中先遇到無限迴圈,接著又出現「左子樹退出後右子樹不顯示」的現象。問題出在:pop 之後若堆疊已空而右子樹還在,流程就無以為繼,而程式並沒有把 NULL 節點壓入堆疊作為哨兵。
int PreOrderTraverseNonRecursive(const BiTree &T, int (*VisitNode)(TElemType data)) {
if (T == NULL) { return -1; }
BiTNode *pBiNode = T;
SqStack S;
InitStack(&S);
Push(&S, (SElemType)T);
while (!IsStackEmpty(S)) {
GetTop(S, (SElemType*)&pBiNode);
while (pBiNode) {
VisitNode(pBiNode->data);
pBiNode = pBiNode->lchild;
Push(&S, (SElemType)pBiNode);
}
if (pBiNode == NULL) {
Pop(&S, (SElemType*)&pBiNode);
}
if (!IsStackEmpty(S)) {
Pop(&S, (SElemType*)&pBiNode);
pBiNode = pBiNode->rchild;
Push(&S, (SElemType)pBiNode);
}
}
return 0;
}
流程是:先壓入根節點,判斷左子樹是否為空,不為空就繼續壓棧;為空則退出迴圈把 NULL 出堆疊,再確認堆疊非空後取出父節點,轉去處理右孩子並壓棧,然後再檢查這個右子樹的左孩子,如此循環。
這個版本代價是兩處浪費:一是把空孩子節點也壓進堆疊,二是頻繁呼叫 GetTop 取堆頂。
回到第一版的思路,它沒有壓入 NULL,卻也無法完整輸出。解法是把「當前節點是否為 NULL」一起放進外層 while 的條件:
// 非遞迴先序遍歷二元樹
int PreOrderTraverseNonRecursiveEx(const BiTree &T,
int (*VisitNode)(TElemType data)) {
if (T == NULL) { return -1; }
BiTNode *pBiNode = T;
SqStack S;
InitStack(&S);
Push(&S, (SElemType)T);
while (!IsStackEmpty(S) || pBiNode) // 主要修改的就是這一句
{
while (pBiNode) {
VisitNode(pBiNode->data);
if (pBiNode != T) {
Push(&S, (SElemType)pBiNode);
}
pBiNode = pBiNode->lchild;
}
if (pBiNode == NULL) {
Pop(&S, (SElemType*)&pBiNode);
}
if (pBiNode->rchild == NULL) {
Pop(&S, (SElemType*)&pBiNode);
}
pBiNode = pBiNode->rchild;
}
return 0;
}
第一個測試用的二元樹:

輸入 12 34 0 0 78 0 0,輸出為 12 34 78,符合預期。
再換一棵結構更複雜的二元樹:

輸入 12 34 24 0 0 50 0 0 78 37 0 0 0,輸出為 12 34 24 50 78 37,與先序遍歷的定義一致,結果正確。
可以。這套骨架不只適用先序。只要把 VisitNode 的呼叫位置從「第一次遇到節點時」移到合適的時機,同樣的結構稍作調整就能改寫成中序或後序遍歷。