C 語言實現二叉樹四種遍歷：遞歸與非遞歸（層序）完整代碼

二叉樹定義與存儲

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

四種遍歷定義

• 先序 (DLR)：根 → 左 → 右
• 中序 (LDR)：左 → 根 → 右
• 後序 (LRD)：左 → 右 → 根
• 層序：逐層從左到右（需隊列輔助）

遞歸實現（先/中/後序）

void PreOrder(BiTree T, void(*visit)(BiTree)) {
    if (T) { visit(T); PreOrder(T->lchild, visit); PreOrder(T->rchild, visit); }
}
void InOrder(BiTree T, void(*visit)(BiTree)) {
    if (T) { InOrder(T->lchild, visit); visit(T); InOrder(T->rchild, visit); }
}
void PostOrder(BiTree T, void(*visit)(BiTree)) {
    if (T) { PostOrder(T->lchild, visit); PostOrder(T->rchild, visit); visit(T); }
}

層序遍歷（隊列實現）

void LevelOrder(BiTree T, void(*visit)(BiTree)) {
    BiTree queue[100]; int front=0, rear=0;
    if (T) queue[rear++] = T;
    while (front != rear) {
        BiTree p = queue[front++];
        visit(p);
        if (p->lchild) queue[rear++] = p->lchild;
        if (p->rchild) queue[rear++] = p->rchild;
    }
}

測試主程序

int main() {
    BiTree T; Init_BiTree(&T); Create_BiTree(&T); // 輸入例：1247###5#8##36###
    PreOrder(T, Print); printf("\n");
    InOrder(T, Print); printf("\n");
    PostOrder(T, Print); printf("\n");
    LevelOrder(T, Print); printf("\n");
    return 0;
}

輸出示例

輸入 1247###5#8##36### 對應樹形圖，輸出：
先序：1 2 4 7 5 8 3 6
中序：7 4 2 8 5 1 6 3
後序：7 4 8 5 2 6 3 1
層序：1 2 3 4 5 6 7 8