C語言二叉樹完全實現：構建、三種遍歷、葉子/節點計數、菜單驅動測試

數據結構定義

typedef struct Node {
    int data;
    struct Node *left, *right;
} Node;

核心操作實現

1. 遞歸構建（先序輸入，0 表示空）

Node* create_tree() {
    int x; scanf("%d", &x);
    if (x == 0) return NULL;
    Node *t = malloc(sizeof(Node));
    t->data = x;
    printf("Input left child of %d: ", x); t->left = create_tree();
    printf("Input right child of %d: ", x); t->right = create_tree();
    return t;
}

2. 三種深度優先遍歷

void preorder(Node *t) {   // 根-左-右
    if (!t) return;
    printf("%d ", t->data);
    preorder(t->left);
    preorder(t->right);
}
void inorder(Node *t) {    // 左-根-右
    if (!t) return;
    inorder(t->left);
    printf("%d ", t->data);
    inorder(t->right);
}
void postorder(Node *t) {  // 左-右-根
    if (!t) return;
    postorder(t->left);
    postorder(t->right);
    printf("%d ", t->data);
}

3. 葉子節點計數

int count_leaves(Node *t) {
    if (!t) return 0;
    if (!t->left && !t->right) return 1;
    return count_leaves(t->left) + count_leaves(t->right);
}

4. 總節點計數

int count_nodes(Node *t) {
    if (!t) return 0;
    return 1 + count_nodes(t->left) + count_nodes(t->right);
}

菜單驅動主程式

int menu() {
    int c;
    puts("\n=== Binary Tree Demo ===");
    puts("1. Create Tree");
    puts("2. Preorder Traversal");
    puts("3. Inorder Traversal");
    puts("4. Postorder Traversal");
    puts("5. Count Leaves");
    puts("6. Count Nodes");
    puts("7. Exit");
    printf("Choice: "); scanf("%d", &c);
    return c;
}

int main() {
    Node *root = NULL;
    int choice;
    while ((choice = menu()) != 7) {
        switch (choice) {
            case 1: printf("Enter nodes (0 for null):\n"); root = create_tree(); puts("Tree created."); break;
            case 2: printf("Preorder: "); preorder(root); putchar('\n'); break;
            case 3: printf("Inorder: "); inorder(root); putchar('\n'); break;
            case 4: printf("Postorder: "); postorder(root); putchar('\n'); break;
            case 5: printf("Leaves: %d\n", count_leaves(root)); break;
            case 6: printf("Total nodes: %d\n", count_nodes(root)); break;
            default: puts("Invalid!");
        }
    }
    return 0;
}

進階擴展方向

1. 非遞歸遍歷：用顯式棧模擬遞歸，避免棧溢出（深度 > 10⁵）。
2. 層序遍歷 (BFS)：隊列實現，應用於樹的寬度、逐層輸出。
3. 二叉搜索樹 (BST) 操作：插入、刪除、查找、第 k 小（中序遍歷計數）。
4. 平衡樹 (AVL/紅黑)：旋轉操作維持高度平衡，保證 O(log n) 查找。
   
5. 序列化/反序列化：先序+空標記 或 層序 存盤/網絡傳輸。
6. 最近公共祖先 (LCA)：遞歸/二分查找（BST）/Tarjan 離線算法。

內存管理提醒

程式退出前應遞歸釋放所有節點：

void free_tree(Node *t) {
    if (!t) return;
    free_tree(t->left);
    free_tree(t->right);
    free(t);
}

Valgrind 檢測無洩漏。