【算法与数据结构】字典树（Trie）详解

目录

一，字典树的定义

二，字典树的代码实现

完整代码+详细注释：

测试用例+测试结果：

三，处理其他字符 

四，内存优化与扩展

1. 内存优化

2. 扩展功能

五，扩展功能支持通配符匹配

六，相关题目

1，实现前缀树

2，添加与搜索单词 - 数据结构设计

---

 

一，字典树的定义

字典树，也叫前缀树或Trie树，是一种树形结构，是一种用于快速检索字符串的数据结构，每个节点代表一个字符，从根节点到某一节点的路径组成一个字符串。主要思想是利用字符串的公共前缀来节省存储空间。

【示例】：

给你n个单词，进行q次查询，每次询问一个单词，让你判断每次查询的字符串是否存在？

我们能想到的是暴力求解，遍历n个字符串，判断是否存在。

对于该问题，查找字符串，就像我们平时查字典的操作。首先确定它的第一个字母，再确定它的第二个字母......，最后就可以找到想要查找的单词。或者这个字符不存在于字典中。

下图是用字典树来存储字符串"abc"，"abb"，"bca"。

 上图中，红色节点表示：有一个以此节点为终点的单词。

比如在查找字符串"abb"时，每个字符都可以在树中查到，并且最后一个字符b节点为红色，说明该字符串存在与该字典树中。查找字符串"bc"时，每个租房有都可以在树种查到，但最后一个字符c节点不为红色，说明该字符串不存在于该字典树中。

从上面的示例中可以看出，对于字典树的每次查询，时间复杂度都是log级别的，比暴力求解更优。

二，字典树的代码实现

字典树的结构，通常每个节点包含一个指向子节点的指针数组，这里我们实现一个处理小写字母的字典树，每个字符对应的下标为ch-'a'，所以数组的大小为26。另外，还需一个标记位来标记是否是单词的结尾。而当前字符保存在哪呢？其实当前节点的字符可以不用保存，因为我们知道下标，加上‘a'，就可以拿到该字符了。

我们主要需要实现三种操作：包含插入、搜索和前缀匹配功能，这里我们用两个函数来实现，然后我们用一个二维数组来实现字典树的建树。

完整代码+详细注释： #include <iostream> #include <vector> using namespace std; //定义节点 struct TrieNode { vector<TrieNode*> children;//存储字节点的指针数组 bool isEnd; //标记位 TrieNode() :children(26, nullptr) , isEnd(false) {} }; class Trie { public: Trie() { root = new TrieNode(); } ~Trie() { clear(root); } //插入单词 void insert(const string& word) { TrieNode* node = root; for (char ch : word) { //计算索引 int index = ch - 'a'; //当前节点为空，当前节点没有存储ch该字母,new一段空间出来 if (node->children[index] == nullptr) node->children[index] = new TrieNode(); //当前节点不为空，也就是当前节点已经存储ch该字母了，在ch的下面节点继续插入下一个字母 node = node->children[index]; } node->isEnd = true; } //搜索单词 bool search(const string& word) { TrieNode* node = root; for (auto ch : word) { //计算索引 int index = ch - 'a'; //当前索引下为空，该字母不存在，则该字符串不存在 if (node->children[index] == nullptr) return false; //当前索引下不为空，该字母存在，继续匹配下一个字母 node = node->children[index]; } //检查最后一个字母是否是结尾 return node->isEnd; } //前缀匹配 bool startsWith(const string& prefix) { TrieNode* node = root; for (auto& ch : prefix) { int index = ch - 'a'; if (node->children[index] == nullptr) return false; node = node->children[index]; } return true; //不检查结尾状态 } private: //递归释放（析构辅助函数） void clear(TrieNode* node) { if (node == nullptr) return; for (int i = 0; i < 26; i++) { if (node->children[i]) clear(node->children[i]); } delete node; } TrieNode* root; //根节点 }; 测试用例+测试结果： int main() { Trie trie; // 插入单词 trie.insert("apple"); trie.insert("app"); trie.insert("banana"); // 搜索测试 cout << boolalpha; cout << "Search 'apple': " << trie.search("apple") << endl; // true cout << "Search 'app': " << trie.search("app") << endl; // true cout << "Search 'appl': " << trie.search("appl") << endl; // false // 前缀匹配测试 cout << "Prefix 'app': " << trie.startsWith("app") << endl; // true cout << "Prefix 'ban': " << trie.startsWith("ban") << endl; // true cout << "Prefix 'cat': " << trie.startsWith("cat") << endl; // false return 0; } 三，处理其他字符 

我们实现的Trie现在只适用于小写字母。

若要支持更多字符（如大写字母，数字，中文等），需要调整字符索引方式：

// 示例：扩展支持大写字母和数字（共62种字符） int getIndex(char c) { if (c >= 'a' && c <= 'z') return c - 'a'; // 0-25 else if (c >= 'A' && c <= 'Z') return 26 + c - 'A'; // 26-51 else if (c >= '0' && c <= '9') return 52 + c - '0'; // 52-61 else throw invalid_argument("Invalid character"); } 四，内存优化与扩展

1. 内存优化

压缩字典树（Radix Tree）：合并只有一个子节点的路径，减少节点数量。

动态分配子节点：使用unordered_map或vector替代固定数组，节省空间（适用于稀疏字符集）。

2. 扩展功能

词频统计：在节点中添加count字段，统计单词出现次数。

前缀自动补全：遍历前缀后的所有分支，收集完整单词。

模糊搜索：支持通配符（如app*e）或编辑距离匹配。

总结：

字典树通过共享前缀高效存储字符串集合，适合前缀匹配和快速检索场景 。

五，扩展功能支持通配符匹配

对于通配符的情况，通常的处理方法是在搜索时遇到通配符时遍历所有可能的子节点。例如，处理"ap？e"时，在遍历到通配符的位置，需要检查所有子节点，继续匹配剩下的模式。这种方法可能需要递归或队列来管理多个可能的路径。

 如下图所示，当遍历到通配符？的位置时，需要遍历所有子节点l和p，然后继续匹配。直到匹配到e结束。

前面我们是通过vector来模拟字典树，这里用哈希表来实现。

那对于一个节点该存什么？一个标记位与前面实现的用途一样，一个哈希表来存字符和子节点的映射关系。通过该字符，可以找到它的所有字节点。

通配符？可以匹配任意单个字符，通配符*可以匹配任意长度字符（包括空）。

代码+注释：

bool wildcardSearch(TrieNode* node, const string& pattern, int pos) { //访问到最后一个位置，直接返回 if (pos == pattern.size()) return node->isEnd; char c = pattern[pos]; if (c == '？') //匹配任意单个字符 { for (auto& pair : node->children) { //尝试匹配所有可能的节点 if (wildcardSearch(pair.second, pattern, pos + 1)); return true; } //走到这，说明*匹配成任何节点都找不到该字符串 return false; } else if (c == '*') //匹配任意长度字符 包括空 { return wildcardSearch(node, pattern, pos + 1) //跳过* || wildcardSearch(node, pattern, pos); //继续匹配当前字符 } else //其他正常情况 { if (node->children.count(c) == 0) return false; return wildcardSearch(node->children[c], pattern, pos+1); } }

完整代码：

#include <iostream> #include <unordered_map> #include <string> using namespace std; struct TrieNode { bool isEnd=false;//结尾标志 unordered_map<char, TrieNode*> children; //存储子节点 }; class FuzzyTrie { public: FuzzyTrie() { root = new TrieNode(); } ~FuzzyTrie() { clear(root); } void insert(const string& word) { //插入逻辑与Trie一样 TrieNode* node = root; for (auto ch : word) { if (node->children[ch] == nullptr) node->children[ch] = new TrieNode(); node = node->children[ch]; } node->isEnd = true; } //通配符搜索接口 bool wildcardMatch(const string& pattern) { return wildcardSearch(root, pattern, 0); } private: //通配符匹配辅助函数 bool wildcardSearch(TrieNode* node, const string& pattern, int pos) { //访问到最后一个位置，直接返回 if (pos == pattern.size()) return node->isEnd; char c = pattern[pos]; if (c == '？') //匹配任意单个字符 { for (auto& pair : node->children) { //尝试匹配所有可能的节点 if (wildcardSearch(pair.second, pattern, pos + 1)); return true; } //走到这，说明*匹配成任何节点都找不到该字符串 return false; } else if (c == '*') //匹配任意长度字符 包括空 { return wildcardSearch(node, pattern, pos + 1) //跳过* || wildcardSearch(node, pattern, pos); //继续匹配当前字符 } else //其他正常情况 { if (node->children.count(c) == 0) return false; return wildcardSearch(node->children[c], pattern, pos+1); } } void clear(TrieNode* node) { if (node == nullptr) return; for (auto& pair : node->children) { clear(pair.second); } delete node; } TrieNode* root; };

 

六，相关题目 1，实现前缀树

题目链接：208. 实现 Trie (前缀树) - 力扣（LeetCode）

class Trie { public: Trie() :children(26),isend(false){} void insert(string word) { Trie* node=this; for(char ch:word) { ch-='a'; if(node->children[ch]==nullptr) node->children[ch]=new Trie(); node=node->children[ch]; } node->isend=true; } Trie* searchPrefix(string prefix) { Trie* node=this; for(char ch:prefix) { ch-='a'; if(node->children[ch]==nullptr) return nullptr; node=node->children[ch]; } return node; } bool search(string word) { Trie* node=this->searchPrefix(word); return node!=nullptr&&node->isend; } bool startsWith(string prefix) { return searchPrefix(prefix)!=nullptr; } private: vector<Trie*> children; bool isend; }; /** * Your Trie object will be instantiated and called as such: * Trie* obj = new Trie(); * obj->insert(word); * bool param_2 = obj->search(word); * bool param_3 = obj->startsWith(prefix); */ 2，添加与搜索单词 - 数据结构设计

题目链接：211. 添加与搜索单词 - 数据结构设计 - 力扣（LeetCode）

struct TrieNode { vector<TrieNode*> children; bool isend; TrieNode():children(26,nullptr),isend(false){} }; void insert(const string& s,TrieNode* root) { TrieNode* node=root; for(char ch:s) { ch-='a'; if(node->children[ch]==nullptr) node->children[ch]=new TrieNode(); node=node->children[ch]; } node->isend=true; } class WordDictionary { public: WordDictionary() { trie=new TrieNode(); } void addWord(string word) { insert(word,trie); } bool search(string word) { //遇到.匹配任意字符 return dfs(word,0,trie); } bool dfs(string& word,int index,TrieNode* node) { if(index==word.size()) return node->isend; char ch=word[index]; if(ch>='a'&&ch<='z') { TrieNode* children=node->children[ch-'a']; if(children!=nullptr&&dfs(word,index+1,children)) return true; } else if(ch=='.') { for(int i=0;i<26;i++) { TrieNode* child=node->children[i]; if(child!=nullptr&&dfs(word,index+1,child)) return true; } } return false; } private: TrieNode* trie; };