二叉樹遍歷全解析：遞歸與非遞歸實現（C++ 模板風格）

二叉樹遍歷全解析：遞歸與非遞歸實現（C++ 模板風格）

二叉樹遍歷是資料結構的核心基本功。本文系統整理先序、中序、後序、層次四大遍歷方式，提供遞歸與非遞歸（顯式棧/隊列）雙重實現，代碼採用現代 C++ 風格，適合教學、面試與工程參考。

節點結構定義

struct BinaryTreeNode {
    BinaryTreeNode* left;
    BinaryTreeNode* right;
    void* data;
};
using VisitFunc = int (*)(void*);  // 訪問回調，返回非0可提前終止

遞歸實現——簡潔直觀

// 先序：根 → 左 → 右
void preOrderR(BinaryTreeNode* root, VisitFunc visit) {
    if (!root) return;
    visit(root->data);
    preOrderR(root->left, visit);
    preOrderR(root->right, visit);
}

// 中序：左 → 根 → 右
void inOrderR(BinaryTreeNode* root, VisitFunc visit) {
    if (!root) return;
    inOrderR(root->left, visit);
    visit(root->data);
    inOrderR(root->right, visit);
}

// 後序：左 → 右 → 根
void postOrderR(BinaryTreeNode* root, VisitFunc visit) {
    if (!root) return;
    postOrderR(root->left, visit);
    postOrderR(root->right, visit);
    visit(root->data);
}

非遞歸實現——顯式棧模擬調用棧

先序遍歷（棧 LIFO，先壓右再壓左）

void preOrder(BinaryTreeNode* root, VisitFunc visit) {
    if (!root) return;
    std::stack st;
    st.push(root);
    while (!st.empty()) {
        auto* node = st.top(); st.pop();
        visit(node->data);
        if (node->right) st.push(node->right);
        if (node->left)  st.push(node->left);
    }
}

中序遍歷（沿左鏈下潛，彈出訪問，轉右）

void inOrder(BinaryTreeNode* root, VisitFunc visit) {
    std::stack st;
    BinaryTreeNode* cur = root;
    while (cur || !st.empty()) {
        if (cur) {
            st.push(cur);
            cur = cur->left;
        } else {
            cur = st.top(); st.pop();
            visit(cur->data);
            cur = cur->right;
        }
    }
}

後序遍歷（雙指標法：p 當前節點，q 最近訪問節點）

void postOrder(BinaryTreeNode* root, VisitFunc visit) {
    std::stack st;
    BinaryTreeNode *p = root, *q = nullptr;
    do {
        while (p) { st.push(p); p = p->left; }
        q = nullptr;
        while (!st.empty()) {
            p = st.top(); st.pop();
            if (!p->right || p->right == q) {
                visit(p->data);
                q = p;
            } else {
                st.push(p);
                p = p->right;
                break;
            }
        }
    } while (!st.empty());
}

層次遍歷（BFS，棧改隊列）

void levelOrder(BinaryTreeNode* root, VisitFunc visit) {
    if (!root) return;
    std::queue q;
    q.push(root);
    while (!q.empty()) {
        auto* node = q.front(); q.pop();
        visit(node->data);
        if (node->left)  q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

中序/後序前驅後繼規律速查

工程落地提示

• 遞歸版代碼極簡，但深度超過 10⁴ 可能棧溢位；生產環境深樹優先用非遞歸
• 非遞歸版可輕鬆加入「暫停/繼續/逐步」功能，適合可視化教學工具
• 回調函式返回非 0 可實現提前終止遍歷（如搜尋到目標即停）
• 若節點含父指標，中序/後序非遞歸可無棧 O(1) 空間實現（Morris 遍歷）

熟練掌握這四種遍歷的遞歸與非遞歸寫法，是解決二叉樹絕大多數問題（序列化、重建、LCA、路徑和等）的基石。