萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

二叉樹先序遍歷非遞歸算法深度解析與 C 語言完整實現

遞歸雖優雅,但深度過大易棧溢出;非遞歸借助顯式棧,可控性更強,也是面試與系統級開發的必考點。本文從算法邏輯推演、常見錯誤剖析、到最終正確的 C 語言實現,層層遞進,帶你徹底攻克二叉樹先序非遞歸遍歷。

一、先序遍歷核心邏輯回顧

先序順序:**根 → 左 → 右**。遞歸版本天然利用調用棧記錄「返回地址」,非遞歸必須手動維護一個棧來模擬這一過程。

關鍵難點:何時訪問右子樹?

  • 訪問完根節點,沿左鏈一直向下,將沿途節點壓棧
  • 左鏈走到底(遇到 NULL),彈棧取出父節點
  • 轉向父節點的右子樹,重複上述過程
  • 棧空且當前節點為 NULL 時結束

二、錯誤代碼剖析(避坑指南)

錯誤版本一:缺少「當前節點非空」作為外層循環條件

while (!IsStackEmpty(S)) {  // 危險:棧空但 pBiNode 指向右子樹非空時會過早退出
    while (pBiNode) { ... }
    Pop(&S, &pBiNode);
    pBiNode = pBiNode->rchild;
}

後果:左子樹遍歷完畢彈棧後,若右子樹存在但棱已空,循環結束導致右子樹遺漏。

錯誤版本二:盲目壓入 NULL 指針

while (pBiNode) {
    VisitNode(pBiNode->data);
    Push(&S, pBiNode);   // 即使 pBiNode->lchild 為 NULL 也壓入
    pBiNode = pBiNode->lchild;
}

後果:棧中混入無效 NULL,彈出時需額外判斷,邏輯複雜且易出錯。

三、正確算法設計:雙條件驅動循環

核心洞見

外層循環條件應為 !IsStackEmpty(S) || pBiNode != NULL,含義:

  • 棧不空 → 還有祖先節點待處理右子樹
  • pBiNode 不空 → 正在下探左鏈或剛轉入右子樹
  • 兩者皆空 → 遍歷結束

標準流程圖解

開始
  ↓
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               // 轉入右子樹
  ↓
結束

四、完整 C 語言實現(含棧結構定義)

1. 數據結構定義

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;
}

2. 訪問回調函數類型

typedef int (*VisitFunc)(TElemType data);
// 返回 0 繼續,非 0 可提前終止遍歷

3. 核心遍歷函數(最終修正版)

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;
}

五、測試驗證

測試用例 1:普通二叉樹

輸入序列(0 代表空):12 34 0 0 78 0 0
樹結構:
      12
     /  \
   34    78
輸出:12 34 78  ✓

測試用例 2:左傾樹 + 右子樹嵌套

輸入: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  ✓

測試用例 3:單右鏈樹(極端情況)

輸入:1 0 2 0 3 0 0
輸出:1 2 3  ✓

六、擴展:中序、後序非遞歸快速轉換

同一棧框架,只需移動 VisitNode() 位置:

  • 中序 (左-根-右):將 VisitNode 移至內層 while 結束、彈棧之後、進右子樹之前
  • 後序 (左-右-根):需額外標記「右子樹已訪問」,或用雙棧法(先序改根-右-左再反轉)

七、總結

  1. 非遞歸先序的靈魂是 while (!stack.empty() || p) 雙條件循環
  2. 「不壓入 NULL」配合「無右子樹雙重彈棧」是極簡正確實現
  3. 指針傳遞用 SElemType* 接收 Pop 結果,避免值拷貝丟失地址
  4. 實際工程中推薦封裝通用棧結構,遍歷函數僅負責邏輯協調

掌握這套模板,不僅能應對面試白板編程,更能在嵌入式、編譯器前端等對棧深度敏感的場景落地。建議動手敲一遍,體會「指針在棧中流動」的節奏感。

copyright © 萬盛學電腦網 all rights reserved