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

C語言遞歸實現二叉樹的先序、中序、後序遍歷

編輯：C 語言入門

遞歸遍歷：最直觀的二叉樹操作

遞歸利用系統調用棧自動管理遍歷狀態，代碼極其簡潔，是教學與輕量級應用的首選。本文展示標準的三種遞歸遍歷實現。

數據結構

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

樹的構造（先序輸入，空格為空節點）

void CreateBiTree(BiTree &T) {
    char ch; scanf("%c", &ch);
    if (ch == ' ') { T = NULL; }
    else {
        T = (BiNode*)malloc(sizeof(BiNode));
        T->data = ch;
        CreateBiTree(T->lchild);  // 遞歸構造左子樹
        CreateBiTree(T->rchild);  // 遞歸構造右子樹
    }
}

三種遍歷核心代碼

// 先序：根 → 左 → 右
void PreOrderTraverse(BiTree T) {
    if (!T) return;
    printf("%c ", T->data);
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
}

// 中序：左 → 根 → 右
void InOrderTraverse(BiTree T) {
    if (!T) return;
    InOrderTraverse(T->lchild);
    printf("%c ", T->data);
    InOrderTraverse(T->rchild);
}

// 後序：左 → 右 → 根
void PostOrderTraverse(BiTree T) {
    if (!T) return;
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    printf("%c ", T->data);
}

測試輸入與輸出

輸入序列（空格代表空節點）：

- + a 空 空 * b 空 空 - c 空 空 d 空 空 / e 空 空 f 空 空

程序將輸出三種遍歷結果，可對照非遞歸版本驗證正確性。

遞歸 vs 非遞歸選擇指南

場景	推薦方式	理由
教學演示、樹高<1000	遞歸	代碼清晰、易理解、維護成本低
嵌入式系統、深度未知、高性能要求	非遞歸	可控棧大小、無棧溢出風險、適合優化
面試、算法題	兩者皆掌握	考察對調用棧與顯式棧的理解深度