字典树（Trie）：快速查单词的“字母树”

你有没有试过在手机输入法里打一个“app”，它会立刻弹出“apple”“appear”这些单词？或者玩单词接龙游戏时，想快速知道有没有以某个字母组合开头的单词？这些场景背后用到的厉害工具，就是 字典树（Trie）。

字典树就像一本超级聪明的“单词索引书”：从根节点出发，每个字母是一条岔路，沿着字母往下走，就能找到所有拥有同一前缀的单词。它专门用来快速存储和查询字符串集合，特别适合做前缀匹配、词频统计、自动补全等任务。

1. 字典树长什么样？

假设我们有一个单词库：{"cat", "car", "dog", "door"}。把这四个单词放进字典树，它的形状就像一棵倒挂的树：

        root
       /    \
      c      d
     / \    / \
    a   a   o   o
   /    \   \   \
  t      r   g   o
                  \
                   r

根节点不存字母，只用来出发。
从根往“c”走，再往“a”走，再往“t”走，就到了单词cat的结尾。
cat和car共享前缀ca，所以它们的字母“c”和“a”是同一个节点，省了不少空间。
每个单词结束时，我们会做一个标记，表示“这里是一个完整单词”。

2. 节点里藏着什么？

字典树每个节点（我们叫它 TrieNode）里放着两样东西：

26个孩子的指针（因为英文小写字母有26个），每个指针指向下一个字母的节点。如果某个字母不存在，指针就是空（nullptr）。
一个布尔标记 isEnd，表示从根到当前节点的字母序列是不是一个完整的单词。

比如，在 cat 的节点里，isEnd = true；在 ca 的节点里，isEnd = false，因为“ca”不是完整单词。

3. 怎么把单词插进去？

插入单词就像在树上画一条新路。例如插入"dog"：

从根开始，看第一个字母 d：根有没有 d 孩子？没有 → 新建一个节点。
走到新节点，看第二个字母 o：当前节点有没有 o 孩子？没有 → 再新建一个。
再走到新节点，看第三个字母 g：同样没有 → 新建一个。
最后，在 g 节点上标记 isEnd = true。

如果插入"door"，前面 d、o 节点已经存在，直接沿着走，然后新建 o 和 r 节点，最后标记 r 为结尾。

4. 怎么查单词或前缀？

查询单词时，沿着字母往下走，如果中途某个字母没有对应的孩子，说明单词不存在；如果走完了所有字母，还得看最后一个节点的 isEnd 是不是 true——只有标记了才算完整单词。

查询前缀时，和查单词一模一样的走法，但最后不需要看 isEnd，只要走完前缀的所有字母就说明前缀存在。

5. 这些例子像生活中的什么？

查字典：你想找“hello”这个词，先翻到“h”区，再找“he”，再找“hel”……字典树就是按字母把书页分成更小的区域，一次只翻到下一页。
自动补全：你打字“ap”，手机立刻把以“ap”开头的单词（app, apple, april…）都列出来。字典树只要从“ap”节点往下遍历所有路径，就能拿到所有候选词。
单词接龙：对方说“cat”，你下一个词必须以“at”开头，你就可以用字典树快速查有没有以“at”开头的单词（比如“at”, “attic”…）。

6. 新手容易掉进的坑

❌ 忘记初始化孩子指针

C++里，new 出来的 TrieNode 里的 children 数组默认是随机值（不是 nullptr），如果不手动把每个都设为 nullptr，后面判断 if (!node->children[idx]) 就可能误判（以为有孩子但实际是野指针）。
一定要在构造函数里写循环初始化：

for (int i = 0; i < 26; i++) children[i] = nullptr;

❌ 查单词时忘记检查 isEnd

比如树里有 "apple"，你查 "app"，虽然沿着 a->p->p 走下来了，但 'p' 节点并没有标记为结尾（因为 "app" 不是完整单词），所以应该返回 false。
记住：查询单词必须看 isEnd，查询前缀才不用看。

❌ 大小写字母没处理好

上面例子只处理小写 a~z，如果单词里有大写字母或其他字符，要提前转成小写，或者扩展孩子数组大小（比如128）。

❌ 内存泄漏

每次 new TrieNode() 都没有 delete，如果程序一直运行或插入大量单词，内存会越占越多。课程练习中可以忽略，但正式项目里需要使用析构函数释放内存，或者改用智能指针。

7. 完整可运行的代码（带详细中文注释）

#include <iostream>
#include <string>
using namespace std;

const int ALPHABET_SIZE = 26;  // 只有小写英文字母

// 字典树节点结构
struct TrieNode {
    TrieNode* children[ALPHABET_SIZE];  // 26个孩子指针（每个字母对应一个下标）
    bool isEnd;                         // 标记从根到当前节点是否是一个完整单词

    // 构造函数：初始化所有孩子为nullptr，isEnd设为false
    TrieNode() {
        for (int i = 0; i < ALPHABET_SIZE; i++) {
            children[i] = nullptr;
        }
        isEnd = false;
    }
};

// 字典树类
class Trie {
private:
    TrieNode* root;  // 根节点（不存字母）

public:
    // 构造函数：创建根节点
    Trie() {
        root = new TrieNode();
    }

    // 插入一个单词（假设全小写）
    void insert(string word) {
        TrieNode* node = root;               // 从根开始
        for (char ch : word) {               // 遍历每个字母
            int idx = ch - 'a';              // 字母转下标 (0~25)
            if (!node->children[idx]) {      // 如果该字母的孩子不存在
                node->children[idx] = new TrieNode();  // 新建节点
            }
            node = node->children[idx];      // 走到孩子节点
        }
        node->isEnd = true;                  // 标记单词结尾
    }

    // 查询单词是否存在（必须完整匹配且是单词结尾）
    bool search(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            int idx = ch - 'a';
            if (!node->children[idx]) return false;  // 中途字母不存在的 → 单词不存在
            node = node->children[idx];
        }
        return node->isEnd;                  // 走完所有字母，必须看是否标记结尾
    }

    // 查询前缀是否存在（只要走完前缀所有字母就存在）
    bool startsWith(string prefix) {
        TrieNode* node = root;
        for (char ch : prefix) {
            int idx = ch - 'a';
            if (!node->children[idx]) return false;  // 中途缺失 → 前缀不存在
            node = node->children[idx];
        }
        return true;                         // 走完了所有字母，前缀一定存在
    }
};

int main() {
    Trie trie;              // 创建一个字典树

    // 插入几个单词
    trie.insert("cat");
    trie.insert("car");
    trie.insert("dog");
    trie.insert("door");

    // 测试查询
    cout << "search(\"car\"): " << trie.search("car") << endl;   // 输出 1（存在）
    cout << "search(\"cat\"): " << trie.search("cat") << endl;   // 输出 1（存在）
    cout << "startsWith(\"do\"): " << trie.startsWith("do") << endl; // 输出 1（是前缀）
    cout << "search(\"door\"): " << trie.search("door") << endl; // 输出 1（存在，刚才插入了）
    cout << "search(\"do\"): " << trie.search("do") << endl;     // 输出 0（不是完整单词）
    cout << "startsWith(\"ca\"): " << trie.startsWith("ca") << endl; // 输出 1
    cout << "startsWith(\"da\"): " << trie.startsWith("da") << endl; // 输出 0

    return 0;
}

运行结果：

search("car"): 1
search("cat"): 1
startsWith("do"): 1
search("door"): 1
search("do"): 0
startsWith("ca"): 1
startsWith("da"): 0

8. 总结与拓展

字典树的核心优势是 时间只和字符串长度有关，和单词数量无关。插入和查询一个长度为 L 的单词只需 O(L) 时间，非常快。但它也有缺点：如果单词数量很少但都很长、没有公共前缀，树会变得稀疏，浪费很多节点指针的空间。

学了字典树，你还能用它做更多事情：

词频统计：在每个节点加一个 int count，插入时加一，就能统计某个单词出现了几次。
最长公共前缀：在树里找到最深的分支点，直到某个节点有多个孩子，就得到了所有单词的共同前缀。
自动补全：先找到前缀节点，然后用深度优先搜索（DFS）遍历该节点下的所有单词路径。

如果想深入学习，还可以了解：

压缩字典树（Radix Tree）：把只有一个孩子的链合并成一个节点，节省空间。
AC自动机：在字典树上加失败指针，实现多模式匹配（比如屏蔽多个敏感词）。
二进制字典树：对整数（二进制位）建立字典树，用来求最大异或值等。

字典树就像程序员工具箱里的“快速查找工具”，掌握了它，解决字符串前缀问题就手到擒来啦！

相关知识点指引：

字符串与字符数组
指针与动态内存分配
深度优先搜索（DFS）
哈希表与字典树对比
后缀树（Suffix Tree）与字典树的关系

字典树——一个能帮你快速查单词的数据结构