【数据结构与算法】第43篇：Trie树（前缀树/字典树）
目录
一、什么是Trie树
1.1 定义
1.2 特点
二、Trie树的实现
2.1 节点结构
2.2 创建节点
2.3 插入单词
2.4 搜索单词
2.5 前缀匹配
2.6 统计以某前缀开头的单词数
三、完整代码演示
四、Trie树的变体
4.1 压缩Trie（Radix Tree）
4.2 三叉Trie（Ternary Search Tree）
五、Trie vs 哈希表
六、实际应用
七、小结
八、思考题
一、什么是Trie树
1.1 定义
Trie树（前缀树/字典树）是一种多叉树，每个节点代表一个字符，从根到某个节点的路径构成一个字符串。
示例：插入"cat","car","dog","do","doggy"
text
root / \ c d / \ a o / \ \ t r g | | | (cat)(car) (dog) | g | (doggy)
1.2 特点
| 优点 | 缺点 |
|---|---|
| 插入/查找时间复杂度 O(L) | 空间消耗大（每个节点固定大小数组） |
| 支持前缀查询 | 字符集大时内存爆炸 |
| 自动排序（字典序） | 不适合频繁删除 |
二、Trie树的实现
2.1 节点结构
c
#include <stdio.h> #include <stdlib.h> #include <string.h> #define ALPHABET_SIZE 26 // 小写字母 typedef struct TrieNode { struct TrieNode *children[ALPHABET_SIZE]; int isEnd; // 是否是一个单词的结尾 int count; // 经过该节点的单词数（可选，用于统计） } TrieNode;2.2 创建节点
c
TrieNode* createNode() { TrieNode *node = (TrieNode*)malloc(sizeof(TrieNode)); for (int i = 0; i < ALPHABET_SIZE; i++) { node->children[i] = NULL; } node->isEnd = 0; node->count = 0; return node; }2.3 插入单词
c
void insert(TrieNode *root, const char *word) { TrieNode *cur = root; int len = strlen(word); for (int i = 0; i < len; i++) { int idx = word[i] - 'a'; if (cur->children[idx] == NULL) { cur->children[idx] = createNode(); } cur = cur->children[idx]; cur->count++; } cur->isEnd = 1; }2.4 搜索单词
c
int search(TrieNode *root, const char *word) { TrieNode *cur = root; int len = strlen(word); for (int i = 0; i < len; i++) { int idx = word[i] - 'a'; if (cur->children[idx] == NULL) { return 0; } cur = cur->children[idx]; } return cur->isEnd; }2.5 前缀匹配
c
int startsWith(TrieNode *root, const char *prefix) { TrieNode *cur = root; int len = strlen(prefix); for (int i = 0; i < len; i++) { int idx = prefix[i] - 'a'; if (cur->children[idx] == NULL) { return 0; } cur = cur->children[idx]; } return 1; }2.6 统计以某前缀开头的单词数
c
int countPrefix(TrieNode *root, const char *prefix) { TrieNode *cur = root; int len = strlen(prefix); for (int i = 0; i < len; i++) { int idx = prefix[i] - 'a'; if (cur->children[idx] == NULL) { return 0; } cur = cur->children[idx]; } return cur->count; }三、完整代码演示
c
#include <stdio.h> #include <stdlib.h> #include <string.h> #define ALPHABET_SIZE 26 typedef struct TrieNode { struct TrieNode *children[ALPHABET_SIZE]; int isEnd; int count; } TrieNode; TrieNode* createNode() { TrieNode *node = (TrieNode*)malloc(sizeof(TrieNode)); for (int i = 0; i < ALPHABET_SIZE; i++) { node->children[i] = NULL; } node->isEnd = 0; node->count = 0; return node; } void insert(TrieNode *root, const char *word) { TrieNode *cur = root; int len = strlen(word); for (int i = 0; i < len; i++) { int idx = word[i] - 'a'; if (cur->children[idx] == NULL) { cur->children[idx] = createNode(); } cur = cur->children[idx]; cur->count++; } cur->isEnd = 1; } int search(TrieNode *root, const char *word) { TrieNode *cur = root; int len = strlen(word); for (int i = 0; i < len; i++) { int idx = word[i] - 'a'; if (cur->children[idx] == NULL) { return 0; } cur = cur->children[idx]; } return cur->isEnd; } int startsWith(TrieNode *root, const char *prefix) { TrieNode *cur = root; int len = strlen(prefix); for (int i = 0; i < len; i++) { int idx = prefix[i] - 'a'; if (cur->children[idx] == NULL) { return 0; } cur = cur->children[idx]; } return 1; } int countPrefix(TrieNode *root, const char *prefix) { TrieNode *cur = root; int len = strlen(prefix); for (int i = 0; i < len; i++) { int idx = prefix[i] - 'a'; if (cur->children[idx] == NULL) { return 0; } cur = cur->children[idx]; } return cur->count; } // 获取所有以某前缀开头的单词（DFS收集） void collectWords(TrieNode *root, char *prefix, int depth, char **result, int *count) { if (root->isEnd) { result[*count] = (char*)malloc((depth + 1) * sizeof(char)); strncpy(result[*count], prefix, depth); result[*count][depth] = '\0'; (*count)++; } for (int i = 0; i < ALPHABET_SIZE; i++) { if (root->children[i] != NULL) { prefix[depth] = 'a' + i; collectWords(root->children[i], prefix, depth + 1, result, count); } } } char** autoComplete(TrieNode *root, const char *prefix, int *returnSize) { // 先找到前缀节点 TrieNode *cur = root; int len = strlen(prefix); for (int i = 0; i < len; i++) { int idx = prefix[i] - 'a'; if (cur->children[idx] == NULL) { *returnSize = 0; return NULL; } cur = cur->children[idx]; } // 收集所有单词 int capacity = cur->count; char **result = (char**)malloc(capacity * sizeof(char*)); char *buffer = (char*)malloc(100 * sizeof(char)); strcpy(buffer, prefix);*returnSize = 0; collectWords(cur, buffer, len, result, returnSize); free(buffer); return result; } void freeTrie(TrieNode *root) { if (root == NULL) return; for (int i = 0; i < ALPHABET_SIZE; i++) { freeTrie(root->children[i]); } free(root); } int main() { TrieNode *root = createNode(); // 插入单词 char *words[] = {"cat", "car", "dog", "do", "doggy", "apple", "app", "application"}; int n = sizeof(words) / sizeof(words[0]); for (int i = 0; i < n; i++) { insert(root, words[i]); } printf("=== Trie树测试 ===\n\n"); // 搜索测试 printf("搜索 'cat': %s\n", search(root, "cat") ? "找到" : "未找到"); printf("搜索 'dog': %s\n", search(root, "dog") ? "找到" : "未找到"); printf("搜索 'do': %s\n", search(root, "do") ? "找到" : "未找到"); printf("搜索 'cafe': %s\n", search(root, "cafe") ? "找到" : "未找到"); // 前缀匹配测试 printf("\n以 'ca' 开头的单词: %s\n", startsWith(root, "ca") ? "存在" : "不存在"); printf("以 'app' 开头的单词: %s\n", startsWith(root, "app") ? "存在" : "不存在"); // 统计前缀数量 printf("\n以 'ca' 开头的单词数: %d\n", countPrefix(root, "ca")); printf("以 'do' 开头的单词数: %d\n", countPrefix(root, "do")); printf("以 'app' 开头的单词数: %d\n", countPrefix(root, "app")); // 自动补全测试 int size; char *prefix = "ca"; char **suggestions = autoComplete(root, prefix, &size); printf("\n自动补全 '%s':\n", prefix); for (int i = 0; i < size; i++) { printf(" %s\n", suggestions[i]); free(suggestions[i]); } free(suggestions); prefix = "app"; suggestions = autoComplete(root, prefix, &size); printf("\n自动补全 '%s':\n", prefix); for (int i = 0; i < size; i++) { printf(" %s\n", suggestions[i]); free(suggestions[i]); } free(suggestions); freeTrie(root); return 0; }运行结果：
text
=== Trie树测试 === 搜索 'cat': 找到 搜索 'dog': 找到 搜索 'do': 找到 搜索 'cafe': 未找到 以 'ca' 开头的单词: 存在 以 'app' 开头的单词: 存在 以 'ca' 开头的单词数: 2 以 'do' 开头的单词数: 3 以 'app' 开头的单词数: 3 自动补全 'ca': ca car cat 自动补全 'app': app apple application
四、Trie树的变体
4.1 压缩Trie（Radix Tree）
将只有一个孩子的节点压缩成一个边，节省空间。
text
普通Trie: 压缩Trie: c c | | a at → isEnd | | t → isEnd ar → isEnd | a (另一个)
4.2 三叉Trie（Ternary Search Tree）
每个节点有三个孩子（小于、等于、大于），适合内存受限场景。
c
typedef struct TSTNode { char ch; struct TSTNode *left; // 小于 struct TSTNode *mid; // 等于 struct TSTNode *right; // 大于 int isEnd; } TSTNode;五、Trie vs 哈希表
| 对比项 | Trie树 | 哈希表 |
|---|---|---|
| 查找时间复杂度 | O(L) | O(1) 平均 |
| 前缀查询 | 支持 | 不支持 |
| 有序遍历 | 支持（字典序） | 不支持 |
| 空间消耗 | 大（每个节点指针数组） | 中 |
| 哈希冲突 | 无 | 有 |
| 适用场景 | 前缀匹配、自动补全 | 精确查找 |
六、实际应用
| 应用 | 说明 |
|---|---|
| 搜索引擎自动补全 | 根据输入前缀推荐搜索词 |
| 拼写检查 | 快速判断单词是否存在 |
| IP路由 | 最长前缀匹配 |
| 单词统计 | 统计文本中单词出现次数 |
| 敏感词过滤 | 高效匹配敏感词列表 |
七、小结
这一篇我们学习了Trie树：
| 操作 | 时间复杂度 | 实现要点 |
|---|---|---|
| 插入 | O(L) | 逐字符创建节点 |
| 搜索 | O(L) | 逐字符查找 |
| 前缀匹配 | O(L) | 同搜索，不检查isEnd |
| 自动补全 | O(L + K) | DFS收集所有单词 |
核心结构：
每个节点有26个指针（小写字母）
isEnd标记单词结尾
count统计经过节点单词数
适用场景：
大量字符串的前缀匹配
自动补全、拼写检查
字典序输出
下一篇我们讲堆的实现（优先队列）。
八、思考题
Trie树的根节点是否代表空字符串？它需要存储字符吗？
如果要处理大小写字母和数字，节点结构如何修改？
如何用Trie树实现单词的删除操作？
Trie树的空间消耗主要在哪里？如何优化？
欢迎在评论区讨论你的答案。