字典樹（Trie）是處理字符串匹配的高效數據結構，廣泛應用于搜索提示、拼寫檢查等場景。本文將帶你從零掌握字典樹的原理與實現！

一、什么是字典樹？

字典樹（Trie）是一種樹形數據結構，用于高效存儲和檢索字符串集合。它的核心優勢在于：

• 前綴共享：具有相同前綴的字符串共享樹中的路徑

• 查找高效：查找時間復雜度僅與字符串長度相關（O(L)）

• 自動排序：存儲的字符串按字典序自動排列

典型應用場景：

1. 搜索引擎的自動補全功能

2. 拼寫檢查與單詞提示

3. IP路由表的最長前綴匹配

4. 單詞游戲（如Boggle、Scrabble）

二、字典樹的核心原理

基本結構

字典樹是一棵多叉樹，每個節點包含：

• 指向子節點的指針數組（通常26個，對應26個字母）

• 結束標記（標識從根到當前節點是否構成完整單詞）

工作方式

假設我們存儲單詞：["cat", "car", "dog"]

結構說明：

根節點 (root)

• 不存儲具體字符

• 包含指向所有首字母子節點的指針

字符節點

• 每個節點存儲一個字符

• 包含 26 個子指針（對應 a-z）

• 示例路徑：

  • root → c → a → t?形成 "cat"

  • root → c → a → r?形成 "car"

  • root → d → o → g?形成 "dog"

單詞結束標記 (*)

• 紅色節點表示單詞結束位置

• t*?標記 "cat" 結束

• r*?標記 "car" 結束

• g*?標記 "dog" 結束

共享前綴機制

• "cat" 和 "car" 共享?c→a?路徑

• 節省存儲空間的關鍵特性

三、C++實現字典樹

節點結構設計

const int ALPHABET_SIZE = 26;class TrieNode {
public:TrieNode* children[ALPHABET_SIZE];bool isEndOfWord; // 標記是否單詞結束TrieNode() {isEndOfWord = false;for (int i = 0; i < ALPHABET_SIZE; i++) {children[i] = nullptr;}}
};

字典樹類框架

class Trie {
private:TrieNode* root;// 遞歸刪除節點（用于析構）void deleteTrie(TrieNode* node) {if (!node) return;for (int i = 0; i < ALPHABET_SIZE; i++) {if (node->children[i]) {deleteTrie(node->children[i]);}}delete node;}public:Trie() {root = new TrieNode();}~Trie() {deleteTrie(root);}// 插入單詞void insert(string word);// 搜索單詞（完全匹配）bool search(string word);// 檢查前綴是否存在bool startsWith(string prefix);
};

關鍵操作實現

1. 插入操作

void Trie::insert(string word) {TrieNode* current = root;for (char c : word) {int index = c - 'a';// 如果字符節點不存在則創建if (!current->children[index]) {current->children[index] = new TrieNode();}current = current->children[index];}current->isEndOfWord = true; // 標記單詞結束
}

2. 搜索操作

bool Trie::search(string word) {TrieNode* current = root;for (char c : word) {int index = c - 'a';if (!current->children[index]) {return false; // 字符不存在}current = current->children[index];}return current->isEndOfWord; // 檢查是否單詞結束
}

3. 前綴檢查

bool Trie::startsWith(string prefix) {TrieNode* current = root;for (char c : prefix) {int index = c - 'a';if (!current->children[index]) {return false;}current = current->children[index];}return true; // 前綴存在
}

四、復雜度分析

操作	時間復雜度	空間復雜度
插入單詞	O(L)	O(L)
搜索單詞	O(L)	O(1)
前綴檢查	O(L)	O(1)

L = 字符串長度

五、實戰應用：自動補全系統

// 獲取以指定前綴開頭的所有單詞
vector<string> getSuggestions(TrieNode* root, string prefix) {vector<string> suggestions;TrieNode* current = root;// 定位到前綴的最后一個節點for (char c : prefix) {int index = c - 'a';if (!current->children[index]) {return suggestions; // 前綴不存在}current = current->children[index];}// DFS收集所有單詞collectWords(current, prefix, suggestions);return suggestions;
}// DFS遍歷收集單詞
void collectWords(TrieNode* node, string currentWord, vector<string>& words) {if (!node) return;if (node->isEndOfWord) {words.push_back(currentWord);}for (int i = 0; i < ALPHABET_SIZE; i++) {if (node->children[i]) {char c = 'a' + i;collectWords(node->children[i], currentWord + c, words);}}
}

六、字典樹的優化方向

1. 內存優化：使用vector動態存儲子節點（犧牲時間換空間）

2. 刪除操作：添加引用計數支持安全刪除

3. 壓縮字典樹：合并只有一個子節點的連續節點

4. 支持Unicode：使用哈希表替代固定數組

七、總結與思考

字典樹的核心價值在于解決字符串前綴匹配問題。相比哈希表：

特性	字典樹	哈希表
前綴搜索	高效支持	不支持
內存占用	較高（空間換時間）	較低
查找效率	O(L)	O(1)平均
自動排序	支持	不支持

適用場景選擇：

• 需要前綴匹配 → 字典樹

• 僅需精確匹配 → 哈希表

• 內存敏感場景 → 三向單詞查找樹

紙上得來終覺淺，絕知此事要躬行！建議嘗試實現字典樹后，在LeetCode上練習相關題目（如208, 211, 212題）鞏固理解。

---

擴展思考：如何修改字典樹結構使其支持中文？歡迎在評論區分享你的思路！