二叉樹遍歷完整指南：遞歸與非遞歸（先序、中序、後序）C++ 實作詳解

編輯：關於C語言

遍歷定義

順序	操作順序	應用場景
先序	根 → 左 → 右	樹的複製、前綴表達式
中序	左 → 根 → 右	BST 排序輸出、中綴表達式
後序	左 → 右 → 根	釋放記憶體、後綴表達式、樹高計算

資料結構定義

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

1. 遞歸演算法（簡潔、教學首選）

// 先序
void PreOrder(BiTree T) {
    if (!T) return;
    visit(T->data);
    PreOrder(T->lchild);
    PreOrder(T->rchild);
}

// 中序
void InOrder(BiTree T) {
    if (!T) return;
    InOrder(T->lchild);
    visit(T->data);
    InOrder(T->rchild);
}

// 後序
void PostOrder(BiTree T) {
    if (!T) return;
    PostOrder(T->lchild);
    PostOrder(T->rchild);
    visit(T->data);
}

缺點：深度過大（>10^4）導致棧溢位；函數呼叫開銷大。

2. 非遞歸演算法（顯式棧、生產級）

先序：根入棧 → 出棧訪問 → 右、左入棧（右先左後，保證左先出）

void PreOrderIter(BiTree root) {
    if (!root) return;
    std::stack st;
    st.push(root);
    while (!st.empty()) {
        BiTree p = st.top(); st.pop();
        visit(p->data);
        if (p->rchild) st.push(p->rchild);
        if (p->lchild) st.push(p->lchild);
    }
}

中序：沿左鏈入棧 → 出棧訪問 → 轉右子樹

void InOrderIter(BiTree root) {
    std::stack st;
    BiTree p = root;
    while (p || !st.empty()) {
        while (p) { st.push(p); p = p->lchild; } // 壓入左鏈
        p = st.top(); st.pop();
        visit(p->data);
        p = p->rchild; // 轉右
    }
}

後序：雙棧法 / 單棧+前驅指標

雙棧法（易理解）：

void PostOrderIter2(BiTree root) {
    if (!root) return;
    std::stack s1, s2;
    s1.push(root);
    while (!s1.empty()) {
        BiTree p = s1.top(); s1.pop();
        s2.push(p);
        if (p->lchild) s1.push(p->lchild);
        if (p->rchild) s1.push(p->rchild);
    }
    while (!s2.empty()) {
        visit(s2.top()->data);
        s2.pop();
    }
}

原理：s1 模擬「根→右→左」，s2 反轉得「左→右→根」。

單棧+前驅指標（空間優化）：

void PostOrderIter(BiTree root) {
    if (!root) return;
    std::stack st;
    BiTree prev = nullptr;
    st.push(root);
    while (!st.empty()) {
        BiTree p = st.top();
        // 正在下探左/右子樹
        if ((p->lchild && prev != p->lchild && prev != p->rchild) ||
            (p->rchild && prev != p->rchild)) {
            if (p->rchild) st.push(p->rchild);
            if (p->lchild) st.push(p->lchild);
        } else { // 子樹已處理完畢
            visit(p->data);
            prev = p;
            st.pop();
        }
    }
}

3. 層序遍歷（BFS，額外補充）

void LevelOrder(BiTree root) {
    if (!root) return;
    std::queue q;
    q.push(root);
    while (!q.empty()) {
        BiTree p = q.front(); q.pop();
        visit(p->data);
        if (p->lchild) q.push(p->lchild);
        if (p->rchild) q.push(p->rchild);
    }
}

4. 由遍歷序列重構樹（面試高頻）

先序 + 中序：先序首為根，在中序定位根分左右，遞歸建構。
中序 + 後序：後序尾為根，同理。
先序 + 後序：無法唯一確定（除非滿二叉樹）。

5. 完整可編譯測試代碼（C++11）

#include 
using namespace std;

struct Node { char val; Node *l, *r; Node(char v):val(v),l(nullptr),r(nullptr){} };

Node* build(const string& pre, const string& in) { /* 略 */ }
void visit(char c) { cout << c << ' '; }

// 上述 6 種遍歷函數...

int main() {
    //       A
    //    B     C
    //  D  E   F
    Node* root = new Node('A');
    root->l = new Node('B'); root->r = new Node('C');
    root->l->l = new Node('D'); root->l->r = new Node('E');
    root->r->l = new Node('F');
    
    cout << "PreOrder  : "; PreOrder(root); cout << endl;
    cout << "PreIter   : "; PreOrderIter(root); cout << endl;
    cout << "InOrder   : "; InOrder(root); cout << endl;
    cout << "InIter    : "; InOrderIter(root); cout << endl;
    cout << "PostOrder : "; PostOrder(root); cout << endl;
    cout << "PostIter2 : "; PostOrderIter2(root); cout << endl;
    cout << "PostIter  : "; PostOrderIter(root); cout << endl;
    cout << "LevelOrder: "; LevelOrder(root); cout << endl;
    return 0;
}

輸出驗證

PreOrder  : A B D E C F
PreIter   : A B D E C F
InOrder   : D B E A F C
InIter    : D B E A F C
PostOrder : D E B F C A
PostIter2 : D E B F C A
PostIter  : D E B F C A
LevelOrder: A B C D E F