字典树（Trie）详解：用C++构建高效字符串前缀匹配结构（从零开始掌握Trie树）

字典树的基本结构

每个字典树节点通常包含以下信息：

• children[26]：指向子节点的指针数组（假设只处理小写字母a-z）
• isEnd：布尔值，标记当前节点是否为某个单词的结尾

例如，插入单词 "cat" 后，字典树会创建 c → a → t 三个节点，并将 t 节点的 isEnd 设为 true。

C++实现字典树

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

#include <iostream>#include <vector>using namespace std;class TrieNode {public:    vector<TrieNode*> children;    bool isEnd;    TrieNode() {        children = vector<TrieNode*>(26, nullptr);        isEnd = false;    }};class Trie {private:    TrieNode* root;public:    Trie() {        root = new TrieNode();    }    // 插入单词    void insert(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(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(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; // 只要路径存在即可    }};// 示例使用int main() {    Trie trie;    trie.insert("apple");    cout << trie.search("apple") << endl;   // 输出: 1 (true)    cout << trie.search("app") << endl;     // 输出: 0 (false)    cout << trie.startsWith("app") << endl; // 输出: 1 (true)    trie.insert("app");    cout << trie.search("app") << endl;     // 输出: 1 (true)    return 0;}

代码解析

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

- insert 方法遍历单词的每个字符，逐层创建节点，最后标记结尾。

- search 不仅要找到路径，还要求最后一个节点的 isEnd 为 true，确保是完整单词。

- startsWith 只需确认前缀路径存在，不要求是完整单词。

应用场景

字典树在实际开发中有广泛应用：

• 搜索引擎自动补全：输入“app”，提示“apple”、“application”等
• 拼写检查器：快速判断单词是否在词典中
• IP路由查找：最长前缀匹配（需扩展为二进制Trie）
• 敏感词过滤：高效匹配文本中的关键词

这些应用都依赖于字典树对字符串前缀匹配的高效支持。

复杂度分析

- 时间复杂度：插入、搜索、前缀匹配均为 O(L)，L 是字符串长度。

- 空间复杂度：最坏情况下 O(ALPHABET_SIZE × N × L)，其中 N 是单词数量。虽然空间开销较大，但换来的是极快的查询速度。

总结

通过本教程，你已经掌握了如何用C++实现一个基本的字典树。字典树是处理字符串集合的强大工具，尤其适合需要频繁进行前缀匹配的场景。希望你能将这一数据结构应用到自己的项目中！

记住关键词：C++字典树、Trie树实现、字符串前缀匹配、高效字符串存储。