目录
一，字典树的定义
二，字典树的代码实现
完整代码+详细注释：
测试用例+测试结果：
三，处理其他字符
四，内存优化与扩展
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;
};
