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]; <pre class='brush:php;toolbar:false;'>TrieNode() { isEnd = false; for (int i = 0; i < 26; i++) { children[i] = nullptr; } }
};
2. Trie类的设计与实现
class Trie { private: TrieNode* root; <p>public: Trie() { root = new TrieNode(); }</p><pre class='brush:php;toolbar:false;'>// 插入一个单词 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"); <pre class='brush:php;toolbar:false;'>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<char, TrieNode*> 替代数组，节省空间。
- 注意内存释放，长时间运行程序应实现析构函数递归删除节点。
- 支持动态扩展，适合自动补全、拼写检查等场景。
基本上就这些。Trie树的关键在于理解“路径即字符串”的结构逻辑，实现清晰且高效。不复杂但容易忽略细节，比如isEnd标志位的设置。