遞歸雖優雅,但深度過大易棧溢出;非遞歸借助顯式棧,可控性更強,也是面試與系統級開發的必考點。本文從算法邏輯推演、常見錯誤剖析、到最終正確的 C 語言實現,層層遞進,帶你徹底攻克二叉樹先序非遞歸遍歷。
先序順序:**根 → 左 → 右**。遞歸版本天然利用調用棧記錄「返回地址」,非遞歸必須手動維護一個棧來模擬這一過程。
while (!IsStackEmpty(S)) { // 危險:棧空但 pBiNode 指向右子樹非空時會過早退出
while (pBiNode) { ... }
Pop(&S, &pBiNode);
pBiNode = pBiNode->rchild;
}
後果:左子樹遍歷完畢彈棧後,若右子樹存在但棱已空,循環結束導致右子樹遺漏。
while (pBiNode) {
VisitNode(pBiNode->data);
Push(&S, pBiNode); // 即使 pBiNode->lchild 為 NULL 也壓入
pBiNode = pBiNode->lchild;
}
後果:棧中混入無效 NULL,彈出時需額外判斷,邏輯複雜且易出錯。
外層循環條件應為 !IsStackEmpty(S) || pBiNode != NULL,含義:
開始
↓
p = 根節點,根入棧
↓
while (棧不空 OR p不空)
while (p不空) // 沿左鏈深入
訪問 p
若 p 非根則入棧
p = p->lchild
// 走到 NULL,需回溯
if (p == NULL) Pop(&S, &p) // 取父節點
if (p->rchild == NULL) // 無右子樹,繼續回溯
Pop(&S, &p) // 再彈一次(取祖父)
p = p->rchild // 轉入右子樹
↓
結束
typedef char TElemType;
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
// 顺序栈
#define MAXSIZE 100
typedef BiTNode* SElemType;
typedef struct {
SElemType data[MAXSIZE];
int top;
} SqStack;
void InitStack(SqStack *S) { S->top = -1; }
int IsStackEmpty(SqStack S) { return S.top == -1; }
int Push(SqStack *S, SElemType e) {
if (S->top == MAXSIZE-1) return 0;
S->data[++S->top] = e; return 1;
}
int Pop(SqStack *S, SElemType *e) {
if (IsStackEmpty(*S)) return 0;
*e = S->data[S->top--]; return 1;
}
typedef int (*VisitFunc)(TElemType data);
// 返回 0 繼續,非 0 可提前終止遍歷
int PreOrderTraverseNonRecursive(const BiTree T, VisitFunc VisitNode) {
if (T == NULL) return -1;
BiTNode *p = T;
SqStack S;
InitStack(&S);
Push(&S, (SElemType)T); // 根節點入棧
while (!IsStackEmpty(S) || p) { // ★ 關鍵修正:雙條件
while (p) { // 一路向左
VisitNode(p->data); // 訪問根
if (p != T) // 根節點已在棧底,無需重複入棧
Push(&S, (SElemType)p);
p = p->lchild; // 深入左子樹
}
if (p == NULL) { // 左鏈到底,回溯
Pop(&S, (SElemType*)&p); // 彈出父節點
}
// ★ 關鍵:若無右子樹,需再彈一次獲取祖父節點
if (p->rchild == NULL) {
if (!IsStackEmpty(S)) // 防止棧下溢
Pop(&S, (SElemType*)&p);
else
p = NULL; // 棧空說明遍歷結束
}
p = p->rchild; // 轉入右子樹(可能為 NULL,下輪外層循環處理)
}
return 0;
}
輸入序列(0 代表空):12 34 0 0 78 0 0
樹結構:
12
/ \
34 78
輸出:12 34 78 ✓
輸入:12 34 24 0 0 50 0 0 78 37 0 0 0
樹結構:
12
/ \
34 78
/ \ /
24 50 37
輸出:12 34 24 50 78 37 ✓
輸入:1 0 2 0 3 0 0 輸出:1 2 3 ✓
同一棧框架,只需移動 VisitNode() 位置:
VisitNode 移至內層 while 結束、彈棧之後、進右子樹之前while (!stack.empty() || p) 雙條件循環SElemType* 接收 Pop 結果,避免值拷貝丟失地址掌握這套模板,不僅能應對面試白板編程,更能在嵌入式、編譯器前端等對棧深度敏感的場景落地。建議動手敲一遍,體會「指針在棧中流動」的節奏感。