【数据结构与算法】第43篇：Trie树（前缀树/字典树）
·
目录
4.2 三叉Trie（Ternary Search Tree）
一、什么是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树的空间消耗主要在哪里？如何优化？
欢迎在评论区讨论你的答案。
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
13
0- 0
已为社区贡献8条内容
所有评论(0)