C 語言二叉搜索樹庫設計：侵入式節點、函數指針多態與非遞歸實現

編輯：關於C語言

C 語言二叉搜索樹庫設計：侵入式節點、函數指針多態與非遞歸實現

二叉搜索樹（BST）是動態集合、符號表的基礎結構。本文展示一個生產級 C 庫：侵入式節點設計、函數指針實現多態比較/分配/釋放、核心操作採用非遞歸迭代避免棧溢出、接口極簡（創建、插入、刪除、查找、銷毀 5 個核心函數）。

侵入式節點與樹結構

struct __tnode { struct __tnode *lc, *rc; };
#define _TREE_HEAD  struct __tnode __tn  // 放在用戶結構體首位

struct tree {                    // 內部樹描述符
    struct __tnode* root;
    pnew_f new_node;             // 節點分配函數
    icmp_f cmp_insert;           // 插入比較
    icmp_f cmp_find;             // 查找/刪除比較
    vdel_f del_node;             // 節點釋放函數
};
typedef struct tree* tree_t;

用戶端使用示例

struct Dict { _TREE_HEAD; char* key; char* value; };
int cmp_insert(void* a, void* b) { return strcmp(((Dict*)a)->key, ((Dict*)b)->key); }
int cmp_find(void* key, void* node) { return strcmp((char*)key, ((Dict*)node)->key); }
tree_t t = tree_create(new_node, cmp_insert, cmp_find, free);

核心操作非遞歸實現精要

插入：迭代尋找插入點

void tree_add(tree_t* proot, void* node) {
    tree_t t = *proot; struct __tnode *n = t->root, *p = NULL;
    if (!n) { t->root = t->new_node(node); return; }
    while (n) {
        int cmp = t->cmp_insert(node, n);
        if (cmp == 0) return; // 已存在
        p = n; n = (cmp < 0) ? n->lc : n->rc;
    }
    if (t->cmp_insert(node, p) < 0) p->lc = t->new_node(node);
    else p->rc = t->new_node(node);
}

刪除：三種情況統一處理

void tree_del(tree_t* proot, void* key) {
    tree_t t = *proot; struct __tnode *n, *p, *s, *ps;
    if (!(n = tree_get(t, key, (void**)&p))) return; // 找不到
    // 1. 至多一個孩子：直接提拔孩子
    if (!n->lc || !n->rc) s = n->lc ? n->lc : n->rc;
    // 2. 兩個孩子：找右子樹最小節點 s 替代
    else {
        for (ps = n, s = n->rc; s->lc; ps = s, s = s->lc);
        if (ps->lc == s) ps->lc = s->rc; else ps->rc = s->rc;
        s->lc = n->lc; s->rc = n->rc;
    }
    // 重新鏈接父節點
    if (!p) t->root = s;
    else if (p->lc == n) p->lc = s; else p->rc = s;
    if (t->del_node) t->del_node(n);
}

查找：返回節點與父節點

void* tree_get(tree_t t, void* key, void** parent) {
    if (parent) *parent = NULL;
    struct __tnode *n = t->root, *p = NULL;
    while (n) {
        int cmp = t->cmp_find(key, n);
        if (cmp == 0) { if (parent) *parent = p; return n; }
        p = n; n = (cmp < 0) ? n->lc : n->rc;
    }
    return NULL;
}

測試驗證：棧上節點與堆上節點雙模式

棧上節點測試：直接傳結構體地址，new_node 返回原指針，del_node 為 NULL，tree_destroy 僅重置根指針。
堆上節點測試：new_node malloc 複製數據，del_node free，tree_destroy 遞歸釋放所有節點，Valgrind 零洩漏。