先序遍歷的遞迴寫法非常直觀,但遞迴本身就是靠呼叫堆棧支撐的。若要改用迴圈,就得自己維護一個堆棧來模擬這件事。本文記錄從「看似正確但會漏節點」到「真正可用」的三個版本演進。
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;
}
這個版本在測試時出現過兩種症狀:無限迴圈,以及左子樹遍歷完畢後右子樹完全不顯示。原因在於沒有把空孩子節點入棧,一旦 pop 之後棧已空但右子樹還在,迴圈就提前結束了。
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 出棧;再判斷棧是否非空,非空則 pop 取得父節點、處理右孩子並壓入,然後繼續檢查該子樹的左孩子。
這個版本能正確輸出,但有兩處浪費:一是把空孩子節點也壓入棧,二是頻繁呼叫 GetTop 取棧頂。
回頭看版本一的思路其實是對的——它本來就不壓入 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:

--- BiTree --- Please Enter BiTree Node data: 12 Please Enter BiTree Node data: 34 Please Enter BiTree Node data: 0 Please Enter BiTree Node data: 0 Please Enter BiTree Node data: 78 Please Enter BiTree Node data: 0 Please Enter BiTree Node data: 0 12 34 78
這棵樹層次太淺,不足以驗證。換一棵較複雜的:

輸入 12 34 24 0 0 50 0 0 78 37 0 0 0:
--- BiTree --- Please Enter BiTree Node data: 12 Please Enter BiTree Node data: 34 Please Enter BiTree Node data: 24 Please Enter BiTree Node data: 0 Please Enter BiTree Node data: 0 Please Enter BiTree Node data: 50 Please Enter BiTree Node data: 0 Please Enter BiTree Node data: 0 Please Enter BiTree Node data: 78 Please Enter BiTree Node data: 37 Please Enter BiTree Node data: 0 Please Enter BiTree Node data: 0 Please Enter BiTree Node data: 0 12 34 24 50 78 37
對照先序「根 → 左 → 右」的定義,輸出順序正確。
這裡保存的是指標位址(轉型為 int 存放),所以 pop 時取的是 &pBiNode 而非 pBiNode。若把宣告改成 BiTree pBiNode 會更容易理解指標的運作。
另外,這套框架不只適用於先序。想改成中序或後序,只要把 VisitNode 的呼叫移到合適的位置(中序:左子樹處理完之後;後序需搭配輔助標記或雙棧),並調整入棧時機即可。