算法入门——字典树（C++实现详解）

字典树（Trie）是处理字符串匹配的高效数据结构，广泛应用于搜索提示、拼写检查等场景。本文将带你从零掌握字典树的原理与实现！

一、什么是字典树？

字典树（Trie）是一种树形数据结构，用于高效存储和检索字符串集合。它的核心优势在于：

前缀共享：具有相同前缀的字符串共享树中的路径
查找高效：查找时间复杂度仅与字符串长度相关（O(L)）
自动排序：存储的字符串按字典序自动排列

典型应用场景：

搜索引擎的自动补全功能
拼写检查与单词提示
IP路由表的最长前缀匹配
单词游戏（如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);}}
}

六、字典树的优化方向

内存优化：使用vector动态存储子节点（牺牲时间换空间）
删除操作：添加引用计数支持安全删除
压缩字典树：合并只有一个子节点的连续节点
支持Unicode：使用哈希表替代固定数组

七、总结与思考

字典树的核心价值在于解决字符串前缀匹配问题。相比哈希表：

特性	字典树	哈希表
前缀搜索	高效支持	不支持
内存占用	较高（空间换时间）	较低
查找效率	O(L)	O(1)平均
自动排序	支持	不支持