二叉樹非遞歸遍歷：棧與隊列的核心操作實現詳解

前言

在二叉樹的遍歷操作中，遞歸雖然代碼簡潔，但在數據量大或系統棧空間受限時，非遞歸實現更具實用價值。本文深入解析前序、中序、後序三種深度優先遍歷的非遞歸算法，以及廣度優先的層次遍歷，重點剖析其核心數據結構——棧與隊列的基本操作實現。

一、二叉樹節點與棧的數據結構定義

首先定義二叉樹節點結構，包含數據域、左孩子指針、右孩子指針：

typedef struct BiNode {
    char data;
    struct BiNode *lchild, *rchild;
} BiNode, *BiTree;

為了實現非遞歸遍歷，我們需要一個能存儲樹節點指針的順序棧。後序遍歷還需記錄節點訪問狀態（如是否已訪問右子樹），因此棧元素結構設計如下：

typedef struct {
    BiTree ptr;      // 指向二叉樹節點
    int tag;         // 狀態標記：0 表示左子樹已處理，1 表示右子樹已處理
} StackNode;

二、棧的基本操作實現

1. 初始化棧

void InitStack(StackNode *s, int maxSize) {
    s->base = (StackNode *)malloc(maxSize * sizeof(StackNode));
    if (!s->base) exit(OVERFLOW);
    s->top = s->base;
    s->stacksize = maxSize;
}

2. 入棧操作

int Push(StackNode *s, BiTree node, int tag) {
    if (s->top - s->base >= s->stacksize) return 0; // 棧滿
    s->top->ptr = node;
    s->top->tag = tag;
    s->top++;
    return 1;
}

3. 出棧操作

int Pop(StackNode *s, BiTree *node, int *tag) {
    if (s->top == s->base) return 0; // 棧空
    s->top--;
    *node = s->top->ptr;
    *tag = s->top->tag;
    return 1;
}

4. 取棧頂元素

int GetTop(StackNode *s, BiTree *node, int *tag) {
    if (s->top == s->base) return 0;
    *node = (s->top - 1)->ptr;
    *tag = (s->top - 1)->tag;
    return 1;
}

5. 判斷棧空

int StackEmpty(StackNode *s) {
    return s->top == s->base;
}

三、非遞歸遍歷算法實現

1. 前序遍歷（根→左→右）

利用棧模擬遞歸過程：訪問根節點，將右子樹入棧，移至左子樹；左子樹為空時出棧處理右子樹。

void PreOrderTraverse(BiTree T) {
    StackNode s; InitStack(&s, 100);
    BiTree p = T;
    while (p || !StackEmpty(&s)) {
        while (p) {
            visit(p->data);      // 訪問根節點
            Push(&s, p, 0);      // 根節點入棧
            p = p->lchild;       // 遍歷左子樹
        }
        if (!StackEmpty(&s)) {
            Pop(&s, &p, NULL);
            p = p->rchild;       // 轉向右子樹
        }
    }
}

2. 中序遍歷（左→根→右）

將節點入棧後不立即訪問，待左子樹遍歷完畢出棧時再訪問，然後轉向右子樹。

void InOrderTraverse(BiTree T) {
    StackNode s; InitStack(&s, 100);
    BiTree p = T;
    while (p || !StackEmpty(&s)) {
        while (p) {
            Push(&s, p, 0);
            p = p->lchild;
        }
        if (!StackEmpty(&s)) {
            Pop(&s, &p, NULL);
            visit(p->data);      // 訪問根節點
            p = p->rchild;       // 遍歷右子樹
        }
    }
}

3. 後序遍歷（左→右→根）

最複雜，需標記節點狀態：首次入棧標記 0（左子樹未訪問），返回時改為 1（右子樹未訪問），再次返回時才訪問。

void PostOrderTraverse(BiTree T) {
    StackNode s; InitStack(&s, 100);
    BiTree p = T;
    while (p || !StackEmpty(&s)) {
        while (p) {
            Push(&s, p, 0);      // 標記 0：左子樹待處理
            p = p->lchild;
        }
        GetTop(&s, &p, &tag);
        if (tag == 0) {          // 左子樹已處理，轉右子樹
            s.top[-1].tag = 1;
            p = p->rchild;
        } else {                 // 右子樹也已處理，訪問根
            Pop(&s, &p, &tag);
            visit(p->data);
            p = NULL;            // 避免重複處理
        }
    }
}

四、層次遍歷與隊列實現

層次遍歷屬於廣度優先搜索（BFS），需用隊列實現先進先出（FIFO）特性。

隊列數據結構定義

typedef struct {
    BiTree *base;   // 動態數組存儲節點指針
    int front, rear; // 隊頭、隊尾索引
    int queuesize;  // 隊列容量
} Queue;

隊列基本操作

// 初始化
void InitQueue(Queue *q, int maxSize) {
    q->base = (BiTree *)malloc(maxSize * sizeof(BiTree));
    q->front = q->rear = 0;
    q->queuesize = maxSize;
}

// 入隊
int EnQueue(Queue *q, BiTree node) {
    if ((q->rear + 1) % q->queuesize == q->front) return 0; // 隊滿
    q->base[q->rear] = node;
    q->rear = (q->rear + 1) % q->queuesize;
    return 1;
}

// 出隊
int DeQueue(Queue *q, BiTree *node) {
    if (q->front == q->rear) return 0; // 隊空
    *node = q->base[q->front];
    q->front = (q->front + 1) % q->queuesize;
    return 1;
}

// 判斷隊空
int QueueEmpty(Queue *q) {
    return q->front == q->rear;
}

層次遍歷算法

void LevelOrderTraverse(BiTree T) {
    if (!T) return;
    Queue q; InitQueue(&q, 100);
    BiTree p;
    EnQueue(&q, T);
    while (!QueueEmpty(&q)) {
        DeQueue(&q, &p);
        visit(p->data);
        if (p->lchild) EnQueue(&q, p->lchild);
        if (p->rchild) EnQueue(&q, p->rchild);
    }
}

五、總結與對比

掌握棧與隊列在樹遍歷中的靈活運用，是數據結構與算法面試、系統開發中的核心基本功。非遞歸寫法雖代碼量稍大，但可控性強，避免了棧溢出風險，工程實踐中極為常見。