二叉樹遍歷全攻略：遞歸與非遞歸實現（前序、中序、後序）

編輯：關於C語言

二叉樹是數據結構的基石，許多高級結構（如紅黑樹、B樹、堆）皆由其演變而來。樹的遞歸定義天然適合遞歸遍歷，代碼簡潔易懂；而非遞歸實現則需借助棧模擬系統調用棧，其中後序遍歷最具挑戰性。本文系統梳理三種遍歷的兩種實現方式。

二叉樹示意圖

一、前序遍歷（根 → 左 → 右）

1. 遞歸實現

void preOrder1(BinTree *root) {
    if (root != NULL) {
        cout << root->data << " ";
        preOrder1(root->lchild);
        preOrder1(root->rchild);
    }
}

2. 非遞歸實現（棧模擬）

核心邏輯： 訪問節點 → 入棧 → 處理左子樹 → 出棧轉向右子樹

void preOrder2(BinTree *root) {
    stack<BinTree*> s;
    BinTree *p = root;
    while (p != NULL || !s.empty()) {
        while (p != NULL) {
            cout << p->data << " ";
            s.push(p);
            p = p->lchild;
        }
        if (!s.empty()) {
            p = s.top(); s.pop();
            p = p->rchild;
        }
    }
}

二、中序遍歷（左 → 根 → 右）

1. 遞歸實現

void inOrder1(BinTree *root) {
    if (root != NULL) {
        inOrder1(root->lchild);
        cout << root->data << " ";
        inOrder1(root->rchild);
    }
}

2. 非遞歸實現

核心邏輯： 一路向左入棧 → 出棧訪問 → 轉向右子樹重複

void inOrder2(BinTree *root) {
    stack<BinTree*> s;
    BinTree *p = root;
    while (p != NULL || !s.empty()) {
        while (p != NULL) {
            s.push(p);
            p = p->lchild;
        }
        if (!s.empty()) {
            p = s.top(); s.pop();
            cout << p->data << " ";
            p = p->rchild;
        }
    }
}

三、後序遍歷（左 → 右 → 根）

1. 遞歸實現

void postOrder1(BinTree *root) {
    if (root != NULL) {
        postOrder1(root->lchild);
        postOrder1(root->rchild);
        cout << root->data << " ";
    }
}

2. 非遞歸實現——方法一：雙次入棧標記法

每個節點會兩次出現在棧頂，第二次才訪問。需額外結構標記是否首次出棧。

struct BTNode {
    BinTree *btnode;
    bool isFirst;
};

void postOrder2(BinTree *root) {
    stack<BTNode*> s;
    BinTree *p = root;
    BTNode *temp;
    while (p != NULL || !s.empty()) {
        while (p != NULL) {
            BTNode *btn = new BTNode{p, true};
            s.push(btn);
            p = p->lchild;
        }
        if (!s.empty()) {
            temp = s.top(); s.pop();
            if (temp->isFirst) {
                temp->isFirst = false;
                s.push(temp);
                p = temp->btnode->rchild;
            } else {
                cout << temp->btnode->data << " ";
                p = NULL;
                delete temp;
            }
        }
    }
}

3. 非遞歸實現——方法二：前驅節點追蹤法（推薦）

利用 pre 記錄上一次訪問的節點，判斷子樹是否已處理完畢。碼更簡潔，無需額外結構。

void postOrder3(BinTree *root) {
    if (!root) return;
    stack<BinTree*> s;
    BinTree *cur = root, *pre = NULL;
    s.push(root);
    while (!s.empty()) {
        cur = s.top();
        // 條件：葉子節點、或左右子樹已被訪問
        if ((cur->lchild == NULL && cur->rchild == NULL) ||
            (pre != NULL && (pre == cur->lchild || pre == cur->rchild))) {
            cout << cur->data << " ";
            s.pop();
            pre = cur;
        } else {
            // 注意：先壓右再壓左，保證左子樹先被處理
            if (cur->rchild) s.push(cur->rchild);
            if (cur->lchild) s.push(cur->lchild);
        }
    }
}