數據結構基石：二叉樹核心概念、存儲結構與遞歸遍歷全解析

二叉樹定義與術語

• 節點：數據元素 + 左/右子樹指針。
• 根節點：無父節點的唯一節點。
• 葉子節點：無子節點。
• 度：子樹個數（0/1/2）。
• 深度/高度：根到節點最長路徑邊數。

特殊二叉樹

存儲結構

鏈式存儲（主流）

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

順序存儲（僅適用完全二叉樹/堆）

#define MAX 100
int tree[MAX];  // 根下標 1，左 2i，右 2i+1

三種遞歸遍歷（深度優先）

void PreOrder(Node *root) {   // 根-左-右
    if (!root) return;
    visit(root->data);
    PreOrder(root->left);
    PreOrder(root->right);
}

void InOrder(Node *root) {      // 左-根-右
    if (!root) return;
    InOrder(root->left);
    visit(root->data);
    InOrder(root->right);
}

void PostOrder(Node *root) {    // 左-右-根
    if (!root) return;
    PostOrder(root->left);
    PostOrder(root->right);
    visit(root->data);
}

應用：前序-複製樹/前綴表達式；中序-BST 輸出有序序列/中綴表達式；後序-釋放樹/後綴表達式。

層序遍歷（廣度優先）

void LevelOrder(Node *root) {
    if (!root) return;
    Node *q[1000]; int front=0, rear=0;
    q[rear++] = root;
    while (front < rear) {
        Node *cur = q[front++];
        visit(cur->data);
        if (cur->left) q[rear++] = cur->left;
        if (cur->right) q[rear++] = cur->right;
    }
}

二叉搜索樹核心操作完整實現

typedef struct { Node *root; int cnt; } BST;

Node* CreateNode(int val) {
    Node *n = malloc(sizeof(Node));
    n->data = val; n->left = n->right = NULL;
    return n;
}

/* 插入 */
void Insert(Node **root, int val) {
    if (!*root) { *root = CreateNode(val); return; }
    if (val < (*root)->data) Insert(&(*root)->left, val);
    else Insert(&(*root)->right, val);
}

/* 查找：返回指向目標節點指針的指針，便於刪除 */
Node** Find(Node **root, int val) {
    if (!*root) return root;
    if (val == (*root)->data) return root;
    return val < (*root)->data ? Find(&(*root)->left, val) : Find(&(*root)->right, val);
}

/* 刪除：合併左右子樹 */
void Delete(Node **root, int val) {
    Node **target = Find(root, val);
    if (!*target) return;
    Node *victim = *target;
    if (victim->left) Insert(&victim->right, victim->left->data); // 簡化：實際應整棵子樹合併
    *target = victim->right; // 此處為簡化演示，完整合併見下文
    free(victim);
}

/* 完整合併刪除 */
void DeleteFull(Node **root, int val) {
    Node **t = Find(root, val);
    if (!*t) return;
    Node *v = *t;
    if (v->left) {
        // 將左子樹插入右子樹
        Node **p = &v->right;
        while (*p) p = (*p)->data > v->left->data ? &(*p)->right : &(*p)->left;
        *p = v->left;
    }
    *t = v->right;
    free(v);
}

非遞歸遍歷（顯式棧）

void InOrderIter(Node *root) {
    Node *stack[1000]; int top = 0;
    Node *p = root;
    while (p || top) {
        while (p) { stack[top++] = p; p = p->left; }
        p = stack[--top];
        visit(p->data);
        p = p->right;
    }
}

總結

1. 二叉樹是數據結構皇冠上的明珠，掌握遞歸思維是關鍵。
2. BST 平均 O(log n)，退化成鏈表 O(n) → 引出 AVL、紅黑樹、Treap 等平衡樹。
3. 實際工程中優先用成熟庫（C++ std::map/set、Linux 內核 rb_tree），手寫僅為理解原理。