二叉樹遞歸遍歷完全指南：前序、中序、後序 C 語言實現與圖解

二叉樹節點定義

typedef int ElemType;
typedef struct BTree {
    ElemType val;
    struct BTree *left;
    struct BTree *right;
} BTree, *PBTree;

核心操作函數

1. 節點創建

PBTree makeNode(ElemType x) {
    PBTree p = (PBTree)malloc(sizeof(BTree));
    p->val = x;
    p->left = p->right = NULL;
    return p;
}

2. BST 插入（教學演示用）

PBTree insert(ElemType x, PBTree *root) {
    if (*root == NULL) return *root = makeNode(x);
    if (x == (*root)->val) return NULL; // 不允許重複
    if (x < (*root)->val) return insert(x, &(*root)->left);
    return insert(x, &(*root)->right);
}

3. 三種遞歸遍歷

void preOrder(PBTree root) {   // 根-左-右
    if (root) {
        visit(root);
        preOrder(root->left);
        preOrder(root->right);
    }
}
void inOrder(PBTree root) {      // 左-根-右
    if (root) {
        inOrder(root->left);
        visit(root);
        inOrder(root->right);
    }
}
void postOrder(PBTree root) {    // 左-右-根
    if (root) {
        postOrder(root->left);
        postOrder(root->right);
        visit(root);
    }
}

測試案例演示

插入序列：{21, 43, 2, 6, 88, 9}
構成樹形結構：

        21
       /  \
      2    43
       \     \
        6     88
         \
          9

前序：21 2 6 9 43 88
中序：2 6 9 21 43 88（BST 中序為升序）
後序：9 6 2 88 43 21

遞歸本質與複雜度

• 時間 O(n)，每個節點訪問一次。
• 空間 O(h)，h 為樹高，最壞 O(n)（鏈表退化），平均 O(log n)。
• 遞歸利用系統調用棧，代碼極簡潔；深度極大時可改寫為顯式棧迭代。