二叉樹四大遍歷演算法完整實作：遞迴與迭代版本對照

二叉樹遍歷是資料結構核心基本功。本文提供前序、中序、後序（深度優先）與層次（廣度優先）四種遍歷的完整 C++ 實作，對照遞迴與迭代寫法，並解析時間空間複雜度與適用場景。

節點定義

struct TreeNode {
    char val;
    TreeNode *left, *right;
    TreeNode(char v) : val(v), left(nullptr), right(nullptr) {}
};

深度優先遍歷（遞迴版）

// 前序
void preorder(TreeNode* root) {
    if (!root) return;
    cout << root->val << ' ';
    preorder(root->left);
    preorder(root->right);
}

// 中序
void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << ' ';
    inorder(root->right);
}

// 後序
void postorder(TreeNode* root) {
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->val << ' ';
}

深度優先遍歷（迭代版：手動堆疊）

遞迴本質是系統呼叫堆疊，手動模擬可避免棧溢位並便於中斷/恢復。

// 前序迭代：根→左→右，堆疊先壓右再壓左
void preorderIter(TreeNode* root) {
    if (!root) return;
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* cur = st.top(); st.pop();
        cout << cur->val << ' ';
        if (cur->right) st.push(cur->right);
        if (cur->left)  st.push(cur->left);
    }
}

// 中序迭代：左→根→右，沿左鏈入棧
void inorderIter(TreeNode* root) {
    stack<TreeNode*> st;
    TreeNode* cur = root;
    while (cur || !st.empty()) {
        while (cur) { st.push(cur); cur = cur->left; }
        cur = st.top(); st.pop();
        cout << cur->val << ' ';
        cur = cur->right;
    }
}

// 後序迭代：左→右→根，雙棧法或單棧+前驅節點
void postorderIter(TreeNode* root) {
    if (!root) return;
    stack<TreeNode*> st1, st2;
    st1.push(root);
    while (!st1.empty()) {
        TreeNode* cur = st1.top(); st1.pop();
        st2.push(cur);
        if (cur->left)  st1.push(cur->left);
        if (cur->right) st1.push(cur->right);
    }
    while (!st2.empty()) {
        cout << st2.top()->val << ' ';
        st2.pop();
    }
}

廣度優先遍歷（層次遍歷）

使用佇列，先進先出，逐層訪問。

void levelorder(TreeNode* root) {
    if (!root) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* cur = q.front(); q.pop();
        cout << cur->val << ' ';
        if (cur->left)  q.push(cur->left);
        if (cur->right) q.push(cur->right);
    }
}

複雜度對照表

選擇指南

• 教學/快速原型：遞迴版最簡潔易讀。
• 生產環境/深度未知：迭代版避免棧溢位。
• 需逐層處理/最短路徑：層次遍歷唯一選擇。
• 後序釋放記憶體：必須用後序（遞迴或迭代），確保子節點先於父節點釋放。

總結

掌握四大遍歷的遞迴與迭代雙重實作，不僅能應對面試考題，更能在實際專案中根據樹的形狀、記憶體限制、處理需求選擇最適合的策略。建議熟練背誦遞迴三式，重點練習迭代中序與後序的堆疊邏輯。