二叉樹核心操作全實現：構建、三序遍歷、葉子統計與節點計數

數據結構定義

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

1. 遞歸構建二叉樹（前序輸入，0表示空）

Node *create_tree(void) {
    int val;
    if (scanf("%d", &val) != 1) return NULL;
    if (val == 0) return NULL;

    Node *node = malloc(sizeof(Node));
    node->data = val;
    printf("輸入 %d 的左子節點: ", val);
    node->left = create_tree();
    printf("輸入 %d 的右子節點: ", val);
    node->right = create_tree();
    return node;
}

輸入示例：1 2 4 0 0 5 0 0 3 0 6 0 0 對應樹：

      1
    /   \
   2     3
  / \     \
 4   5     6

2. 三種深度優先遍歷

void preorder(Node *root) {
    if (!root) return;
    printf("%d ", root->data);
    preorder(root->left);
    preorder(root->right);
}

void inorder(Node *root) {
    if (!root) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

void postorder(Node *root) {
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->data);
}

3. 葉子節點計數

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

4. 總節點計數

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

5. 非遞歸實現（棧模擬）

// 非遞歸前序
void preorder_iter(Node *root) {
    if (!root) return;
    Node *stack[100];
    int top = 0;
    stack[top++] = root;
    while (top) {
        Node *cur = stack[--top];
        printf("%d ", cur->data);
        if (cur->right) stack[top++] = cur->right;
        if (cur->left)  stack[top++] = cur->left;
    }
}

// 非遞歸中序
void inorder_iter(Node *root) {
    Node *stack[100], *cur = root;
    int top = 0;
    while (cur || top) {
        while (cur) { stack[top++] = cur; cur = cur->left; }
        cur = stack[--top];
        printf("%d ", cur->data);
        cur = cur->right;
    }
}

6. 層序遍歷（隊列）

void level_order(Node *root) {
    if (!root) return;
    Node *queue[1000];
    int head = 0, tail = 0;
    queue[tail++] = root;
    while (head < tail) {
        Node *cur = queue[head++];
        printf("%d ", cur->data);
        if (cur->left)  queue[tail++] = cur->left;
        if (cur->right) queue[tail++] = cur->right;
    }
}

7. 完整測試主程序

int main() {
    printf("請輸入根節點 (0=空): ");
    Node *root = create_tree();

    printf("\n前序: "); preorder(root);
    printf("\n中序: "); inorder(root);
    printf("\n後序: "); postorder(root);
    printf("\n層序: "); level_order(root);
    printf("\n葉子數: %d", count_leaves(root));
    printf("\n總節點: %d\n", count_nodes(root));

    // 釋放內存（後序釋放）
    void free_tree(Node *r) {
        if (r) { free_tree(r->left); free_tree(r->right); free(r); }
    }
    free_tree(root);
    return 0;
}

複雜度與遞歸深度

⚠ 深度超過系統棧限制（通常10⁴-10⁵）會棧溢出，深度大時必須用非遞歸版本。