C 語言非遞歸實現二叉樹三種遍歷：顯式棧模擬、兩種先序/中序寫法、後序訪問計數法

編輯：關於C語言

C 語言非遞歸實現二叉樹三種遍歷

遞歸雖簡潔，但深度不可控時會爆棧。非遞歸版本用顯式棧模擬調用棧，適合生產環境與深度未知樹。本文給出兩種先序/中序寫法、後序訪問計數法、完整動態棧實現與測試驗證。

棧結構與基本操作

#define INIT_STACK_SIZE 100
#define STACK_INCREMENT 10

typedef struct {
    BiNode **base, **top;
    int stacksize;
} SqStack;

void InitStack(SqStack *S) {
    S->base = malloc(INIT_STACK_SIZE * sizeof(BiNode*));
    S->top = S->base;
    S->stacksize = INIT_STACK_SIZE;
}
void Push(SqStack *S, BiNode *e) {
    if (S->top - S->base >= S->stacksize) {
        S->base = realloc(S->base, (S->stacksize + STACK_INCREMENT) * sizeof(BiNode*));
        S->top = S->base + S->stacksize;
        S->stacksize += STACK_INCREMENT;
    }
    *S->top++ = e;
}
void Pop(SqStack *S, BiNode **e) { *e = *--S->top; }
int GetTop(SqStack S, BiNode **e) { if (S.base == S.top) return 0; *e = *(S.top - 1); return 1; }
int StackEmpty(SqStack S) { return S.base == S.top; }

節點結構 (含訪問計數供後序)

typedef struct BiNode {
    char data;
    struct BiNode *lchild, *rchild;
    int visitcount;  // 後序用：0=未訪, 1=左歸來, 2=右歸來
} BiNode, *BiTree;

先序遍歷兩種寫法

// 寫法 1：外層 while + 內層向左到底
void PreorderTraverse_1(BiTree T) {
    SqStack S; InitStack(&S); Push(&S, T);
    BiTree p;
    while (!StackEmpty(S)) {
        while (GetTop(S, &p) && p) {
            printf("%c ", p->data);
            Push(&S, p->lchild);
        }
        Pop(&S, &p);           // 彈出 NULL
        if (!StackEmpty(S)) {
            Pop(&S, &p);       // 彈出父節點
            Push(&S, p->rchild);
        }
    }
}

// 寫法 2：統一 while (p || !empty) — 教科書標準模式
void PreorderTraverse_2(BiTree T) {
    SqStack S; InitStack(&S);
    BiTree p = T;
    while (p || !StackEmpty(S)) {
        if (p) {
            printf("%c ", p->data);
            Push(&S, p);
            p = p->lchild;
        } else {
            Pop(&S, &p);
            p = p->rchild;
        }
    }
}

中序遍歷兩種寫法

// 寫法 1：外層 while + 內層向左到底
void InOrderTraverse_1(BiTree T) {
    SqStack S; InitStack(&S); Push(&S, T);
    BiTree p;
    while (!StackEmpty(S)) {
        while (GetTop(S, &p) && p) Push(&S, p->lchild);
        Pop(&S, &p);           // 彈出 NULL
        if (!StackEmpty(S)) {
            Pop(&S, &p);
            printf("%c ", p->data);
            Push(&S, p->rchild);
        }
    }
}

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

後序遍歷：訪問計數法

void PostOrderTraverse(BiTree T) {
    SqStack S; InitStack(&S);
    BiTree p = T;
    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///
先序方法1: - + a * b * - c d / e f
先序方法2: - + a * b * - c d / e f
中序方法1: a + b * * c - d - e / f
中序方法2: a + b * * c - d - e / f
後序:      a b * * + c d - e f / -

四種輸出完全一致，驗證非遞歸邏輯正確。

非遞歸 vs 遞歸對比

維度	遞歸	非遞歸
代碼長度	極短	中等 (需棧管理)
棧溢出風險	有 (深度受限)	無 (堆分配棧可擴展)
可讀性	高	中 (後序較複雜)
效能	函數調用開銷	手動棧操作，略快
適用場景	教學、深度可控	生產、深度未知、嵌入式