高效字符串检索利器：C++前缀树（Trie树）从入门到实战应用

为什么使用Trie树？

• 插入和查询的时间复杂度为 O(L)，其中 L 是字符串长度，与字典中单词总数无关。
• 非常适合实现自动补全、拼写建议、词频统计等功能。
• 节省空间（相比哈希表），尤其当字符串有大量公共前缀时。

C++实现一个基础Trie树

下面我们用C++数据结构教程中最清晰的方式，一步步构建一个支持插入、搜索和前缀匹配的Trie。

1. 定义Trie节点

struct TrieNode {    bool isEnd;                     // 标记是否为某个单词的结尾    std::unordered_map children; // 子节点映射    TrieNode() : isEnd(false) {}};

2. 实现Trie类

class Trie {private:    TrieNode* root;public:    Trie() {        root = new TrieNode();    }    // 插入一个单词    void insert(const std::string& word) {        TrieNode* node = root;        for (char c : word) {            if (node->children.find(c) == node->children.end()) {                node->children[c] = new TrieNode();            }            node = node->children[c];        }        node->isEnd = true; // 标记单词结束    }    // 搜索完整单词是否存在    bool search(const std::string& word) {        TrieNode* node = findNode(word);        return node != nullptr && node->isEnd;    }    // 检查是否有以prefix开头的单词    bool startsWith(const std::string& prefix) {        return findNode(prefix) != nullptr;    }private:    // 辅助函数：查找前缀对应的节点    TrieNode* findNode(const std::string& prefix) {        TrieNode* node = root;        for (char c : prefix) {            if (node->children.find(c) == node->children.end()) {                return nullptr;            }            node = node->children[c];        }        return node;    }};

实战：自动补全功能

利用Trie树，我们可以轻松实现输入前缀后返回所有可能的完整单词。这是搜索引擎和输入法中常见的字符串匹配算法应用。

// 在Trie类中添加以下方法void getWords(TrieNode* node, std::string current,               std::vector& result) {    if (node->isEnd) {        result.push_back(current);    }    for (auto& pair : node->children) {        getWords(pair.second, current + pair.first, result);    }}std::vector autoComplete(const std::string& prefix) {    std::vector result;    TrieNode* node = findNode(prefix);    if (node) {        getWords(node, prefix, result);    }    return result;}

完整使用示例

#include <iostream>#include <vector>#include <unordered_map>#include <string>// 此处插入上面定义的 TrieNode 和 Trie 类int main() {    Trie trie;    trie.insert("apple");    trie.insert("app");    trie.insert("application");    trie.insert("apply");    std::cout << "Search 'app': " << trie.search("app") << std::endl;        // 输出 1    std::cout << "Search 'appl': " << trie.search("appl") << std::endl;       // 输出 0    std::cout << "Starts with 'app': " << trie.startsWith("app") << std::endl; // 输出 1    auto suggestions = trie.autoComplete("app");    std::cout << "Auto-complete for 'app':\n";    for (const auto& word : suggestions) {        std::cout << "  " << word << std::endl;    }    return 0;}

总结

通过本教程，你已经掌握了C++前缀树的基本原理与实现方法。Trie树不仅在理论上有优势，在实际工程中也有广泛应用，如网络路由表、文本编辑器的关键词高亮、敏感词过滤等。希望你能将所学的Trie树实现技巧运用到自己的项目中！

记住，掌握好这类字符串匹配算法和C++数据结构教程中的核心内容，将极大提升你的编程能力与面试竞争力。