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; return; }
    *T = 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

先序輸入序列** (空格用 `_` 表示)**：

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

-+a**b***c---d///e///f///  (共 31 字符，含 16 個空格)

先序遍歷結果為: - + a * b * - c d / e f
中序遍歷結果為: a + b * * c - d - e / f
後序遍歷結果為: a b * * + c d - e f / -

int main(void) {
    BiTree T;
    puts("請按先序輸入二叉樹節點 (空格表示空):");
    CreateBiTree(&T);
    puts("先序遍歷結果為:"); PreOrderTraverse(T); putchar('\n');
    puts("中序遍歷結果為:"); InOrderTraverse(T); putchar('\n');
    puts("後序遍歷結果為:"); PostOrderTraverse(T); putchar('\n');
    return 0;
}