Trie树通过共享前缀高效处理字符串操作。1. 结构上每个节点含26个子指针和isEnd标记，表示字符路径与单词结尾；2. Trie类实现insert插入字符路径并标记结尾，search逐层匹配且检查isEnd确保完整单词，startsWith仅判断前缀路径存在性；3. 示例中插入"apple"和"app"后，search与startsWith正确返回布尔结果；4. 优化建议包括用map支持更大字符集、添加析构函数释放内存，适用于自动补全等场景。核心在于路径即字符串的逻辑，需注意isEnd设置细节。
实现一个Trie树（字典树）在C++中主要用于高效处理字符串相关问题，比如前缀匹配、单词查找等。它的核心思想是利用字符串的公共前缀来减少查询时间。
1. Trie树的基本结构
Trie树是一种多叉树结构，每个节点代表一个字符，从根到某节点的路径构成一个字符串前缀。通常设计如下：
- 每个节点包含一个子节点数组（或map），用于指向下一个字符。
- 一个布尔标记，表示该节点是否为某个单词的结尾。
假设只处理小写字母 a-z，可以用大小为26的指针数组来表示子节点。
定义节点结构如下：
立即学习“C++免费学习笔记（深入）”；
struct TrieNode {
bool isEnd;
TrieNode* children[26];
TrieNode() {
isEnd = false;
for (int i = 0; i < 26; i++) {
children[i] = nullptr;
}
}};
2. Trie类的设计与实现
封装TrieNode，提供插入、查找和前缀判断功能。
class Trie {
private:
TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
// 插入一个单词
void insert(const string& word) {
TrieNode* node = root;
for (char c : word) {
int idx = c - 'a';
if (!node->children[idx]) {
node->children[idx] = new TrieNode();
}
node = node->children[idx];
}
node->isEnd = true;
}
// 查找是否完整存在某个单词
bool search(const string& word) {
TrieNode* node = root;
for (char c : word) {
int idx = c - 'a';
if (!node->children[idx]) {
return false;
}
node = node->children[idx];
}
return node->isEnd;
}
// 判断是否存在以prefix为前缀的单词
bool startsWith(const string& prefix) {
TrieNode* node = root;
for (char c : prefix) {
int idx = c - 'a';
if (!node->children[idx]) {
return false;
}
node = node->children[idx];
}
return true;
}};
3. 使用示例
下面是一个简单使用方式：
int main() {
Trie trie;
trie.insert("apple");
trie.insert("app");
cout << trie.search("app") << endl; // 输出 1 (true)
cout << trie.search("apple") << endl; // 输出 1 (true)
cout << trie.startsWith("ap") << endl; // 输出 1 (true)
cout << trie.search("apply") << endl; // 输出 0 (false)
return 0;}
4. 注意事项与优化建议
实际应用中可根据需求调整实现方式：
- 若字符集较大（如含大写字母、数字），可改用 unordered_map
替代数组，节省空间。
- 注意内存释放，长时间运行程序应实现析构函数递归删除节点。
- 支持动态扩展，适合自动补全、拼写检查等场景。
基本上就这些。Trie树的关键在于理解“路径即字符串”的结构逻辑，实现清晰且高效。不复杂但容易忽略细节，比如isEnd标志位的设置。
