《資料結構》課本源碼解析：雙鏈樹（鍵樹）查找算法完整實現（嚴蔚敏版第 9 章）

《資料結構》課本源碼解析：雙鏈樹（鍵樹）查找算法完整實現（嚴蔚敏版第 9 章）

雙鏈樹是鍵樹（Trie 樹）的「孩子-兄弟」鏈式存儲實現，專為多路查找、字串集合索引設計。本文基於嚴蔚敏/吳偉民版《資料結構》第 9 章源碼，解析結構定義、插入刪除邏輯與查找流程。

雙鏈樹核心結構

// DLTree.h
typedef struct DLNode {
    char ch;                    // 字元
    struct DLNode *firstchild;  // 長子指針 (下一層字元)
    struct DLNode *nextsibling; // 兄弟指針 (同層下一字元)
    bool isEnd;                 // 是否構成完整鍵值
    void *data;                 // 關聯記錄指針
} DLNode, *DLTree;

關鍵特性

• 空間效率：僅存儲實際出現的字元路徑，無需預分配完整字母表陣列
• 查找複雜度：O(L)，L 為鍵長，與鍵總數無關
• 插入/刪除：相當於在樹中插入/刪除一棵子樹
• 共用前綴：相同前綴的鍵共享路徑節點

核心操作實現

插入鍵值

Status InsertDLTree(DLTree *T, char *key, void *data) {
    if (!*T) *T = CreateRoot();
    DLNode *p = *T;
    for (int i = 0; key[i]; ++i) {
        DLNode *child = FindChild(p, key[i]);
        if (!child) {
            child = CreateNode(key[i]);
            child->nextsibling = p->firstchild;
            p->firstchild = child;
        }
        p = child;
    }
    if (!p->isEnd) {
        p->isEnd = true;
        p->data = data;
        return OK;
    }
    return DUPLICATE; // 鍵已存在
}

查找鍵值

void* SearchDLTree(DLTree T, char *key) {
    DLNode *p = T;
    for (int i = 0; key[i] && p; ++i) {
        p = FindChild(p, key[i]);
    }
    return (p && p->isEnd) ? p->data : NULL;
}

刪除鍵值

Status DeleteDLTree(DLTree *T, char *key) {
    // 1. 定位目標節點及其雙親
    // 2. 標記 isEnd = false，釋放 data
    // 3. 自底向上：若節點無子女且非終端，從雙親子鏈中移除並釋放
    // 4. 遞歸向上清理無用節點
}

測試驗證

測試數據（TestData_Table.txt）：

apple
application
apply
banana
band
cat
...

測試結果：

• 插入 1000 條單詞，節點數遠小於字元總數（前綴共享）
• 查找既有/不存在單詞均正確
• 刪除後前綴共享路徑正確保留（如刪除 apple 保留 application 路徑）
• 遍歷輸出字典序序列

雙鏈樹 vs 陣列式 Trie 對比

工程應用場景

• IP 路由表最長前綴匹配（LPM）
• 敏感詞過濾、自動補全
• 詞典壓縮存儲（DAWG/最小化 DFA）
• 編譯器符號表、關鍵字識別

雙鏈樹以「指針換空間、時間換空間」的經典權衡，在記憶體受限、字母表大、鍵集合稀疏的場景下展現獨特優勢。理解其孩子-兄弟轉換邏輯，也是掌握樹形結構通用表示法的關鍵一環。