二叉樹遍歷大全：遞歸與非遞歸實現（前中後序+層序）

結構定義

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

遞歸遍歷（簡潔）

void PreOrder(BiTNode* r) { if(!r) return; visit(r); PreOrder(r->lchild); PreOrder(r->rchild); }
void InOrder (BiTNode* r) { if(!r) return; InOrder(r->lchild); visit(r); InOrder(r->rchild); }
void PostOrder(BiTNode* r){ if(!r) return; PostOrder(r->lchild); PostOrder(r->rchild); visit(r); }

非遞歸前序：棧模擬

void PreOrder_NR(BiTree T) {
    if(!T) return;
    stack<BiTree> s; s.push(T);
    while(!s.empty()) {
        BiTree p = s.top(); s.pop();
        visit(p);
        if(p->rchild) s.push(p->rchild); // 右先入
        if(p->lchild) s.push(p->lchild); // 左後入 → 先出
    }
}

非遞歸中序：沿左鏈入棧

void InOrder_NR(BiTree T) {
    stack<BiTree> s; BiTree p = T;
    while(p || !s.empty()) {
        while(p) { s.push(p); p = p->lchild; }
        p = s.top(); s.pop();
        visit(p);
        p = p->rchild;
    }
}

非遞歸後序：雙棧法（易懂）

void PostOrder_NR2(BiTree T) {
    stack<BiTree> s1, s2; s1.push(T);
    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()); s2.pop(); }
}

層序遍歷：隊列

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

輔助功能

• 樹高：max(h(l), h(r)) + 1
• 節點數：1 + cnt(l) + cnt(r)
• 建樹：前序輸入，# 表示空

完整可運行代碼

見原文，包含菜單驅動主程序，可交互測試所有遍歷。