【数据结构与算法】第43篇：Trie树（前缀树/字典树）

目录一、什么是Trie树1.1 定义1.2 特点二、Trie树的实现2.1 节点结构2.2 创建节点2.3 插入单词2.4 搜索单词2.5 前缀匹配2.6 统计以某前缀开头的单词数三、完整代码演示四、Trie树的变体4.1 压缩TrieRadix Tree4.2 三叉TrieTernary Search Tree五、Trie vs 哈希表六、实际应用七、小结八、思考题一、什么是Trie树1.1 定义Trie树前缀树/字典树是一种多叉树每个节点代表一个字符从根到某个节点的路径构成一个字符串。示例插入cat,car,dog,do,doggytextroot / \ 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 创建节点cTrieNode* 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 插入单词cvoid 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 搜索单词cint 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 前缀匹配cint 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 统计以某前缀开头的单词数cint 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 压缩TrieRadix Tree将只有一个孩子的节点压缩成一个边节省空间。text普通Trie: 压缩Trie: c c | | a at → isEnd | | t → isEnd ar → isEnd | a (另一个)4.2 三叉TrieTernary Search Tree每个节点有三个孩子小于、等于、大于适合内存受限场景。ctypedef 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树的空间消耗主要在哪里如何优化欢迎在评论区讨论你的答案。