C語言非遞歸實現二叉樹的先序、中序、後序遍歷

非遞歸遍歷二叉樹：棧模擬遞歸過程

遞歸雖然代碼簡潔，但深度過大時易導致棧溢出。非遞歸算法通過顯式棧結構模擬系統調用棧，更適合嵌入式或大數據場景。本文提供兩套先序、中序遍歷實現及一套後序遍歷實現。

數據結構定義

#define INIT_STACK_SIZE 100
#define STACKINCREMENT 10

// 二叉樹節點
typedef struct BiNode {
    char data;
    struct BiNode *lchild, *rchild;
    int visitcount;  // 後序遍歷用：記錄訪問次數
} BiNode, *BiTree;

// 順序棧
typedef struct {
    BiNode **base;
    BiNode **top;
    int stacksize;
} SqStack;

棧基本操作

void InitStack(SqStack &S) { /* 初始化 */ }
void Push(SqStack &S, BiNode *e) { /* 入棧，支持動態擴容 */ }
void Pop(SqStack &S, BiNode **e) { /* 出棧 */ }
int GetTop(SqStack S, BiNode **e) { /* 取棧頂 */ }
int StackEmpty(SqStack S) { /* 判空 */ }

先序遍歷：方法一（模擬遞歸邏輯）

void PreorderTraverse_1(BiTree T) {
    BiTree p; SqStack S;
    InitStack(S); Push(S, T);
    while (!StackEmpty(S)) {
        while (GetTop(S, &p) && p) {
            printf("%c ", p->data);  // 訪問根
            Push(S, p->lchild);      // 左子樹入棧
        }
        Pop(S, &p);                 // 空指針出棧
        if (!StackEmpty(S)) {
            Pop(S, &p);             // 根節點出棧
            Push(S, p->rchild);     // 右子樹入棧
        }
    }
}

先序遍歷：方法二（更直觀的迭代寫法）

void PreorderTraverse_2(BiTree T) {
    BiTree p = T; SqStack S;
    InitStack(S);
    while (p || !StackEmpty(S)) {
        if (p) {
            printf("%c ", p->data);
            Push(S, p);
            p = p->lchild;
        } else {
            Pop(S, &p);
            p = p->rchild;
        }
    }
}

中序遍歷：方法一

void InOrderTraverse_1(BiTree T) {
    SqStack S; BiTree p;
    InitStack(S); Push(S, T);
    while (!StackEmpty(S)) {
        while (GetTop(S, &p) && p) {
            Push(S, p->lchild);  // 一路向左
        }
        Pop(S, &p);             // 空指針出棧
        if (!StackEmpty(S)) {
            Pop(S, &p);
            printf("%c ", p->data);  // 訪問根
            Push(S, p->rchild);      // 轉向右
        }
    }
}

中序遍歷：方法二（標準迭代模板）

void InOrderTraverse_2(BiTree T) {
    BiTree p = T; SqStack S;
    InitStack(S);
    while (p || !StackEmpty(S)) {
        if (p) {
            Push(S, p);
            p = p->lchild;
        } else {
            Pop(S, &p);
            printf("%c ", p->data);
            p = p->rchild;
        }
    }
}

後序遍歷（利用 visitcount 標記）

void PostOrderTraverse(BiTree T) {
    SqStack S; BiTree p = T;
    InitStack(S);
    while (p || !StackEmpty(S)) {
        if (p) {
            if (p->visitcount != 2) {
                p->visitcount = 1;
                Push(S, p);
            }
            p = p->lchild;
        } else {
            Pop(S, &p);
            if (p->visitcount == 2) {
                printf("%c ", p->data);  // 雙子樹均訪問完，輸出
            } else {
                p->visitcount++;
                Push(S, p);
            }
            p = p->rchild;
        }
    }
}

測試用例構造

輸入序列（空格代表空節點）：

- + a 空 空 * b 空 空 - c 空 空 d 空 空 / e 空 空 f 空 空

對應二叉樹結構見圖片，可驗證四種遍歷結果一致性。

關鍵點總結

• 先序：根→左→右，入棧順序：右、左（棧先進後出）
• 中序：左→根→右，需「走到最左、訪問、轉右」
• 後序：左→右→根，最複雜，需標記節點訪問狀態（0/1/2次）
• 所有算法時間複雜度 O(n)，空間複雜度 O(h)（h為樹高）