C++字典树实现详解（Trie树从入门到实战）

什么是字典树（Trie）？

字典树（Trie）是一种树形数据结构，专门用于存储和检索字符串集合。它的核心思想是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。

例如，单词 "apple"、"app"、"apply" 共享前缀 "app"，在字典树中只需构建一次 "a → p → p" 的路径，后续分支再分别延伸。

为什么使用字典树？

• 插入和查找的时间复杂度为 O(L)，L 是字符串长度，与总词数无关。
• 非常适合自动补全、拼写检查、IP路由等场景。
• 节省空间（相比哈希表存储大量相似前缀的字符串）。

C++字典树的基本结构设计

每个 Trie 节点通常包含：

• 一个指向子节点的指针数组（或 map）
• 一个布尔值，标记当前节点是否为某个单词的结尾

由于英文小写字母只有 26 个，我们可以用大小为 26 的数组来表示子节点。

完整代码实现（C++）

下面是一个完整的 C++前缀树 实现，包含插入、查找和前缀匹配功能：

#include <iostream>#include <string>using namespace std;class TrieNode {public:    bool isEnd; // 标记是否为单词结尾    TrieNode* children[26]; // 26个小写字母    TrieNode() {        isEnd = false;        for (int i = 0; i < 26; ++i) {            children[i] = nullptr;        }    }};class Trie {private:    TrieNode* root;public:    Trie() {        root = new TrieNode();    }    // 插入单词    void insert(const string& word) {        TrieNode* node = root;        for (char c : word) {            int index = c - 'a';            if (node->children[index] == nullptr) {                node->children[index] = new TrieNode();            }            node = node->children[index];        }        node->isEnd = true; // 标记单词结束    }    // 查找完整单词是否存在    bool search(const string& word) {        TrieNode* node = root;        for (char c : word) {            int index = c - 'a';            if (node->children[index] == nullptr) {                return false;            }            node = node->children[index];        }        return node->isEnd; // 必须是单词结尾    }    // 判断是否有以 prefix 开头的单词    bool startsWith(const string& prefix) {        TrieNode* node = root;        for (char c : prefix) {            int index = c - 'a';            if (node->children[index] == nullptr) {                return false;            }            node = node->children[index];        }        return true; // 只需路径存在即可    }    // 可选：析构函数（简化版，实际项目建议用智能指针）    ~Trie() {        deleteNode(root);    }private:    void deleteNode(TrieNode* node) {        if (node == nullptr) return;        for (int i = 0; i < 26; ++i) {            if (node->children[i]) {                deleteNode(node->children[i]);            }        }        delete node;    }};// 测试示例int main() {    Trie trie;    trie.insert("apple");    trie.insert("app");    trie.insert("apply");    cout << "search('app'): " << trie.search("app") << endl;        // 输出 1 (true)    cout << "search('appl'): " << trie.search("appl") << endl;      // 输出 0 (false)    cout << "startsWith('ap'): " << trie.startsWith("ap") << endl;   // 输出 1 (true)    return 0;}

代码解析

- TrieNode 类定义了每个节点的结构，包含 26 个子节点指针和一个结束标志。

- insert 方法逐字符遍历单词，若路径不存在则创建新节点，最后标记结尾。

- search 不仅要路径存在，还要求终点 isEnd == true。

- startsWith 只需路径存在即可，不要求是完整单词。

应用场景举例

• 搜索引擎自动补全：用户输入“py”，系统返回“python”、“pycharm”等建议。
• 拼写检查器：快速判断用户输入的单词是否在词典中。
• IP 路由查找：利用二进制 Trie（如 Radix Tree）高效匹配最长前缀。

优化与扩展

上述实现适用于小写字母。若需支持大小写、数字或 Unicode 字符，可将 children 改为 unordered_map，这样更灵活但略慢。

此外，还可添加删除单词、统计前缀出现次数等功能，进一步提升实用性。

总结

通过本教程，你已经掌握了 字符串高效查找 的利器——字典树（Trie）。它结构清晰、效率高，是处理字符串集合的理想选择。希望你能动手实现并应用到自己的项目中！

记住关键词：C++字典树实现、Trie树教程、C++前缀树、字符串高效查找。这些是你深入学习和面试准备的重要概念！