Trie树是一种用于高效字符串前缀操作的树形结构，节点代表字符、路径构成字符串，共享公共前缀以节省空间；支持O(L)插入、搜索与前缀匹配，常用于自动补全和拼写检查。
什么是Trie树（字典树）
Trie树是一种专门用于高效处理字符串前缀操作的树形结构，常用于自动补全、拼写检查、IP路由查找等场景。它的核心特点是：每个节点代表一个字符，从根到某节点的路径构成一个字符串；所有公共前缀共享同一段路径，节省空间且加速前缀匹配。
基础节点设计与插入逻辑
每个节点不需要存字符本身（由父节点到子节点的边隐式表示），只需记录子节点指针和是否为单词结尾。C++中常用red">unordered_map
插入字符串时，从根出发，逐字符向下走：若对应子节点不存在则新建；遍历完所有字符后，将末节点的isEnd设为true。
- 只处理小写字母时，可用children[c - 'a']快速索引
- 支持任意ASCII字符，推荐用unordered_map避免空间浪费
- 插入过程时间复杂度为O(L)，L为字符串长度
前缀匹配与单词搜索实现
搜索一个完整单词，需走到末节点且该节点isEnd == true；判断是否存在某前缀，只需成功走到对应位置即可，不要求isEnd为真。
立即学习“C++免费学习笔记（深入）”；
例如：已插入"apple"、"app"，那么search("app")返回true，startsWith("appl")也返回true。
- search()：遍历字符，中途遇到空指针返回false；结束时检查isEnd
- startsWith()：同样遍历，但只需确认能走完全程，不检查isEnd
- 两者都不修改结构，纯读操作，线性时间完成
完整可运行示例（小写英文版）
以下是一个轻量、无内存泄漏风险的实现，含构造、插入、搜索、前缀判断功能：
class Trie {
struct TrieNode {
TrieNode* children[26] = {}; // 初始化为nullptr
bool isEnd = false;
};
TrieNode* root;
public:
Trie() : root(new TrieNode()) {}
void insert(const string& word) {
TrieNode* p = root;
for (char c : word) {
if (!p->children[c - 'a']) p->children[c - 'a'] = new TrieNode();
p = p->children[c - 'a'];
}
p->isEnd = true;
}
bool search(const string& word) {
TrieNode* p = root;
for (char c : word) {
if (!p->children[c - 'a']) return false;
p = p->children[c - 'a'];
}
return p->isEnd;
}
bool startsWith(const string& prefix) {
TrieNode* p = root;
for (char c : prefix) {
if (!p->children[c - 'a']) return false;
p = p->children[c - 'a'];
}
return true;
}
};
注意：实际工程中建议补充析构函数释放内存，或改用智能指针；若需支持Unicode或多语言，应替换为unordered_map
基本上就这些 —— Trie树不复杂但容易忽略细节，比如isEnd标记位置、大小写处理、边界空字符串判断等，写对了前缀匹配效率就稳了。
