二叉查找樹 C 實現全解析：插入、查找、刪除、遍歷、銷毀與通用設計模式

二叉查找樹 C 實現全解析：插入、查找、刪除、遍歷、銷毀與通用設計模式

二叉查找樹 (BST) 是經典數據結構，查找/插入/刪除平均 O(log n)。本文通過精簡代碼，完整實現 BST 核心操作，深度講解刪除三種情況、父節點查找技巧、尾遞歸優化、接口設計、測試驅動開發，並拓展 C 語言通用數據結構設計模式 (對象模式、泛型模式、內存對齊技巧)。

一、數據結構定義

typedef int node_t;  // 數據類型，易於替換

typedef struct tree {
    node_t v;           // 節點值
    struct tree *lc;    // 左孩子
    struct tree *rc;    // 右孩子
} *tree_t;              // 類型別名：指向節點的指針

二、核心操作實現

1. 查找節點 & 父節點 (雙返回值技巧)

// 查找值為 v 的節點，找到返回節點指針，否則 NULL
tree_t tree_search(tree_t root, node_t v) {
    while (root) {
        if (root->v == v) return root;
        root = (root->v > v) ? root->lc : root->rc;
    }
    return NULL;
}

// 查找 v 的父節點，順帶返回 v 節點指針 (通過 pn 輸出參數)
// 返回父節點指針，v為根節點或不存在時返回 NULL
tree_t tree_parent(tree_t root, node_t v, tree_t *pn) {
    tree_t p = NULL;
    while (root) {
        if (root->v == v) break;
        p = root;
        root = (root->v > v) ? root->lc : root->rc;
    }
    if (pn) *pn = root; // 順帶返回孩子節點
    return p;
}

設計亮點：一個函數完成「找父」與「找子」兩件事，輸出參數 pn 返回目標節點，調用者無需二次查找。

2. 插入節點

void tree_insert(tree_t *proot, node_t v) {
    tree_t n, p = NULL, t = *proot;
    // 1. 找到插入位置的父節點 p
    while (t) {
        if (t->v == v) return; // 不允許重複值
        p = t;
        t = (t->v > v) ? t->lc : t->rc;
    }
    // 2. 分配新節點
    n = calloc(1, sizeof(struct tree));
    if (!n) exit(EXIT_FAILURE); // 分配失敗直接退出
    n->v = v;
    // 3. 掛接
    if (!p) *proot = n;           // 空樹，作為根
    else if (p->v > v) p->lc = n; // 作為左孩子
    else p->rc = n;               // 作為右孩子
}

3. 刪除節點 (核心難點，三種情況統一處理)

void tree_delete(tree_t *proot, node_t v) {
    tree_t root, n, p, t;
    if (!proot || !(root = *proot)) return;
    
    // 1. 找到目標節點 n 及其父節點 p
    p = tree_parent(root, v, &n);
    if (!n) return; // 不存在
    
    // 情況1/2：n 至多有一個孩子 (葉子 或 單分支)
    // 統一技巧：t 指向 n 的唯一孩子 (或 NULL)
    if (!n->lc || !n->rc) {
        t = n->lc ? n->lc : n->rc; // 找到唯一孩子 (或 NULL)
        if (!p) *proot = t;        // 刪除根節點
        else if (p->lc == n) p->lc = t; // 父節點收養孩子
        else p->rc = t;
        free(n);
        return;
    }
    
    // 情況3：n 有兩個孩子
    // 策略：用右子樹中最小節點 (後繼者) 替代 n
    for (t = n->rc; t->lc; t = t->lc); // 找到右子樹最左節點
    n->v = t->v;                       // 值替換 (不動指針，高效)
    // 遞歸刪除右子樹中的後繼節點 (它至多只有右孩子)
    tree_delete(&n->rc, t->v);         // 尾遞歸優化點
}

刪除三種情況圖解

情況1: 葉子節點          情況2: 單孩子節點         情況3: 兩個孩子
    5                        5                          5
   / \                      / \                        / \
  3   7                    3   7                      3   8
     /                        \                        /   / \
    6                          6                      6   7   9
刪除 6 → 直接免             刪除 7 → 父節點收養 6      刪除 5 → 用 6 替代 5
                                                         遞歸刪除右子樹的 6

4. 中序遍歷打印 (遞歸)

void tree_print(tree_t root) {
    if (root) {
        tree_print(root->lc);
        printf("%d ", root->v);
        tree_print(root->rc);
    }
}

5. 銷毀整棵樹 (後序遍歷釋放)

static void __tree_destroy(tree_t root) {
    if (root) {
        __tree_destroy(root->lc);
        __tree_destroy(root->rc);
        free(root);
    }
}
void tree_destroy(tree_t *proot) {
    if (proot) __tree_destroy(*proot);
    *proot = NULL; // 置空根指針，防野指針
}

三、接口設計與測試驅動 (TDD 風格)

// 接口聲明 (頭文件風格)
void tree_insert(tree_t *proot, node_t v);
void tree_print(tree_t root);
tree_t tree_search(tree_t root, node_t v);
tree_t tree_parent(tree_t root, node_t v, tree_t *pn);
void tree_delete(tree_t *proot, node_t v);
void tree_destroy(tree_t *proot);

// 測試主函數
int main() {
    tree_t root = NULL;
    node_t a[] = {8,4,5,11,2,3,7,-1,9,0,1,13,12,10};
    
    // 1. 批量插入
    for (int i=0; iv : -1);
    
    // 4. 刪除測試
    tree_delete(&root, 8); TREE_PRINT(root); // 刪除根(兩孩子)
    tree_delete(&root, 9); TREE_PRINT(root); // 刪除單分支
    
    // 5. 銷毀
    tree_destroy(&root);
    return 0;
}

四、C 語言通用數據結構設計模式 (拓展)

模式1：一切皆對象

struct otree {
    void *obj;           // 指向任意數據
    struct otree *lc, *rc;
};
struct my_data { int id; char *name; };
// 使用：tree->obj = &my_data_instance;
// 缺點：額外 4/8 字節指針開銷，類型不安全

模式2：宏實現泛型

#define TREE_NODE struct tree_node *lc, *rc
struct tree_node { TREE_NODE; };

struct my_tree {
    TREE_NODE;           // 必須放第一行！便於容器指針轉換
    int id;
    char *name;
};
// 容器指針 → 節點指針：(struct tree_node*)my_tree_ptr
// 節點指針 → 容器指針：需計算偏移量 (offsetof) 或容器宏
// 缺點：調試困難，宏污染命名空間

模式3：內存對齊技巧

struct mem_storage {
    union {
        int align;       // 強制對齊到 int/指針 大小
        void *str;
    } mem;
    // ...
};
// 作用：確保結構體起始地址滿足最嚴格對齊要求，提升跨平台移植性

模式4：清理屬性模擬 RAII (GCC/Clang 擴展)

void cleanup_release(void **p) { if (*p) free(*p), *p=NULL; }

void usage() {
    char *p = malloc(100);
    __attribute__((cleanup(cleanup_release))) char *auto_p = p;
    // 作用域結束自動調用 cleanup_release(&auto_p)
}

五、編碼習慣精進

1. 聲明即初始化：struct sockaddr_in addr = {AF_INET}; (C99 指定初始化器，其餘自動置 0)，避免 memset。
2. 允許爛開始，堅持完美收尾：malloc → 用完 → free → 指針置NULL，防野指針。
3. 尾遞歸優化：刪除雙孩子節點時 tree_delete(&n->rc, t->v) 是尾調用，編譯器可優化為跳轉，不增棧深度。
4. 錯誤處理宏：CERR(fmt,...) 統一打印文件/函數/行號/errno，CERR_EXIT 打印並退出。

六、總結

BST 實現的核心難點在於刪除操作的三種情況統一處理與父子指針重連。通過「查找父節點順帶返回目標節點」、「單/雙分支統一用孩子指針 t」、「雙孩子用後繼者值替換+尾遞歸刪除後繼」三大技巧，代碼精簡高效。接口先行、測試驅動、通用設計模式掌握，讓 C 語言也能寫出優雅、可復用的數據結構庫。