您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

二叉樹非遞歸遍歷完全指南：前序、中序、後序三種實現 (京東 2015 筆試真題)

編輯：C++ 入門

背景

京東 2015 校招筆試編程題：二叉樹前序遍歷非遞歸實現。本文系統總結三種遍歷的遞歸與非遞歸代碼，並給出完整可運行程序。

一、前序遍歷 (根-左-右)

遞歸

void preOrder1(TreeNode* root) {
    if (root) {
        visit(root);
        preOrder1(root->left);
        preOrder1(root->right);
    }
}

非遞歸 (棧模擬)

規則：訪問節點 → 入棧 → 走左子樹；左子樹盡頭 → 出棧 → 走右子樹。

void preOrder2(TreeNode* root) {
    stack st;
    TreeNode* p = root;
    while (p || !st.empty()) {
        while (p) {
            visit(p);
            st.push(p);
            p = p->left;
        }
        p = st.top(); st.pop();
        p = p->right;
    }
}

二、中序遍歷 (左-根-右)

遞歸

void inOrder1(TreeNode* root) {
    if (root) {
        inOrder1(root->left);
        visit(root);
        inOrder1(root->right);
    }
}

非遞歸

規則：一路向左入棧；無左子樹 → 出棧訪問 → 轉右子樹。

void inOrder2(TreeNode* root) {
    stack st;
    TreeNode* p = root;
    while (p || !st.empty()) {
        while (p) {
            st.push(p);
            p = p->left;
        }
        p = st.top(); st.pop();
        visit(p);
        p = p->right;
    }
}

三、後序遍歷 (左-右-根) — 最難

遞歸

void postOrder1(TreeNode* root) {
    if (root) {
        postOrder1(root->left);
        postOrder1(root->right);
        visit(root);
    }
}

非遞歸方法一：雙次入棧標記法

每個節點入棧兩次：第一次標記 isFirst=true，遇到時改標記並轉右子樹；第二次出棧時訪問。

struct Wrapper { TreeNode* node; bool isFirst; };
void postOrder2(TreeNode* root) {
    stack st;
    TreeNode* p = root;
    while (p || !st.empty()) {
        while (p) {
            st.push({p, true});
            p = p->left;
        }
        Wrapper w = st.top(); st.pop();
        if (w.isFirst) {
            w.isFirst = false;
            st.push(w);
            p = w.node->right;
        } else {
            visit(w.node);
            p = nullptr;
        }
    }
}

非遞歸方法二：前驅節點法 (推薦，更簡潔)

維護 pre 指向上一次訪問的節點。棧頂節點 cur 滿足：無孩子、或孩子已被訪問 (pre 是其左/右孩子) → 訪問並出棧；否則按右、左順序入棧孩子。

void postOrder3(TreeNode* root) {
    stack st;
    TreeNode *cur = root, *pre = nullptr;
    st.push(root);
    while (!st.empty()) {
        cur = st.top();
        if ((!cur->left && !cur->right) ||
            (pre && (pre == cur->left || pre == cur->right))) {
            visit(cur);
            st.pop();
            pre = cur;
        } else {
            if (cur->right) st.push(cur->right);
            if (cur->left) st.push(cur->left);
        }
    }
}