【算法与数据结构】字典树（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;    // truecout << "Search 'app': " << trie.search("app") << endl;        // truecout << "Search 'appl': " << trie.search("appl") << endl;      // false// 前缀匹配测试cout << "Prefix 'app': " << trie.startsWith("app") << endl;    // truecout << "Prefix 'ban': " << trie.startsWith("ban") << endl;    // truecout << "Prefix 'cat': " << trie.startsWith("cat") << endl;    // falsereturn 0;
}

三，处理其他字符 

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

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

// 示例：扩展支持大写字母和数字（共62种字符）
int getIndex(char c) {if (c >= 'a' && c <= 'z') return c - 'a';          // 0-25else if (c >= 'A' && c <= 'Z') return 26 + c - 'A'; // 26-51else if (c >= '0' && c <= '9') return 52 + c - '0'; // 52-61else 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;
};