Trie 樹（字典樹）原理與 C++ 實現詳解

什麼是 Trie 樹？

Trie 樹，又稱字典樹或前綴樹，是一種多叉樹結構，本質上是哈希樹的變體。它利用字符串的公共前綴來節省存儲空間，實現極快的字符串檢索、統計與排序，廣泛應用於搜索引擎詞頻統計、自動補全、IP 路由匹配等場景。

核心結構

• 每個節點包含：isStr 標記是否構成完整字符串；next[26] 指向 26 個小寫字母子節點的指針陣列。
• 根節點不儲存字符，從根向下每條邊代表一個字符，路徑即字符串。

完整 C++ 實現

#include <iostream>
#include <cstring>
using namespace std;

const int BRANCH_NUM = 26;

struct TrieNode {
    bool isStr;
    TrieNode* next[BRANCH_NUM];
    TrieNode() : isStr(false) {
        memset(next, 0, sizeof(next));
    }
};

class Trie {
public:
    Trie() : root(new TrieNode()) {}
    ~Trie() { deleteTrie(root); }

    void insert(const char* word);
    bool search(const char* word) const;

private:
    TrieNode* root;
    void deleteTrie(TrieNode* node);
};

void Trie::insert(const char* word) {
    TrieNode* cur = root;
    while (*word) {
        int idx = *word - 'a';
        if (!cur->next[idx])
            cur->next[idx] = new TrieNode();
        cur = cur->next[idx];
        ++word;
    }
    cur->isStr = true;
}

bool Trie::search(const char* word) const {
    TrieNode* cur = root;
    while (*word && cur) {
        cur = cur->next[*word - 'a'];
        ++word;
    }
    return cur && cur->isStr;
}

void Trie::deleteTrie(TrieNode* node) {
    for (int i = 0; i < BRANCH_NUM; ++i)
        if (node->next[i])
            deleteTrie(node->next[i]);
    delete node;
}

int main() {
    Trie t;
    t.insert("a");
    t.insert("abandon");
    t.insert("abandoned");
    t.insert("abashed");
    cout << (t.search("abashed") ? "true" : "false") << '\n';
    return 0;
}

進階應用：字符串哈希映射

在節點額外存儲 hash_value，配合遞增變量 v，可為每個唯一字符串分配唯一整數 ID：

1. 初始化 v = 1。
2. 插入字符串時，若節點 isStr 由 false 變 true，賦值 hash_value = v++；否則直接讀取已有 hash_value。

此法可在允許極低碰撞率的場景替代傳統哈希函數，且天然支持前綴查詢。

優缺點分析

總結

Trie 樹是處理大規模字符串集合的利器，掌握其節點設計、插入查找邏輯及記憶體釋放模式，能在面試與工程實戰中遊刃有餘。