Olverae Assets

1 一句话定义

要又快又省地存一大堆字符串、还能秒判"某个开头是不是已存的词"——字典树（Trie）的招数是：不在节点里存整串，而是每条边代表一个字符，从根走下来的路径连起来才是字符串；再用一个 isEnd 标记说清"这条路径到这儿，是不是一个完整单词"。

像查纸质字典：相同开头的词挤在同一沓里。Trie 让共享前缀只存一份——"car / card / cat" 的 "ca" 只画一次。查或插一个长度 L 的词，只走 L 步，跟字典里已经有多少词毫无关系。唯一要小心的：走到路径末尾，必须看 isEnd 才能区分"这是个词"还是"只是别人的前缀"。

存了 to · tea · in · inn 四个词。绿圈节点 = isEnd=true（一个完整单词的结尾）。注意 in 既是绿圈（自己是单词）又往下接了一个 n（是 inn 的前缀）——这正是 isEnd 存在的理由。

2 模型 · 字符串怎么"逐字下落"

分两小步：第 1 步先用查词器弄懂"路径 = 字符串、isEnd 区分单词与前缀"这条核心；第 2 步看插入/查找时，cur 怎么沿着字符一格一格往下走。

第 1 步 · 查词器：是单词？还是只是前缀？（输入看看）

字典里已存 cat · car · card · dog · do。输入一个词，它会从根逐字符往下走：每个字母若有对应的边就变绿、走通；走到末尾再看那个节点的 isEnd，给出三种结论之一

查

试试 car（是单词）、ca（只是前缀）、cab（路断了）、do（是单词，虽然它也是 dog 的前缀）。"能走通"只说明它是某些词的前缀；"是不是已存单词"完全由终点的 isEnd 决定。代码里这一步就是 cur = cur->child[s[i]-'a']，走完再看 cur->isEnd。

节点在代码里长什么样

一个节点不存字符串，只存：①是不是某个词的结尾；②指向 26 个孩子（a~z）的指针，空位就是 NULL。

struct node {
    bool isEnd;             // 这个节点是不是某个单词的结尾
    struct node *child[26]; // 26 个孩子位，对应 a~z
};

// 造一个新节点：还不是结尾，26 个孩子全空
struct node *newNode(void) {
    struct node *n = malloc(sizeof(struct node));
    n->isEnd = false;                  // 必须显式置 false
    for (int i = 0; i < 26; i++) n->child[i] = NULL;
    return n;
}

字符怎么变成孩子下标？c = s[i] - 'a'：'a'→0、'b'→1、…、'z'→25。下面就来看 insert / search 怎么用它一行行往下走。

第 2 步 · 看代码一行行跑。右边是真实 C 代码，随动画逐行高亮。三个例子：插入会复用已有前缀、只在缺口处新建节点；查找的关键全在最后一行——走到了还不够，必须 isEnd 才算单词。点例子，再点 ▶ 慢慢看（建议 0.5×）。

Trie 插入 / 查找演示

真实 C 代码（当前执行行高亮）

颜色说明

当前节点 cur isEnd=true（一个完整单词）新建的节点

提示

点上方一个例子，再点 ▶ 看 cur 怎么逐字符下落。

树里的词数（isEnd 节点数）

—

本次结论

3 核心要点 · 4 句人话看懂 Trie

每张卡片先用一句大白话说清"它到底在讲什么"，再配最小例子。

① 路径即字符串（节点不存整串）

一句话：别再想"一个节点装一个单词"。每条边一个字符，从根走到某节点的那条路，连起来才是字符串。

所以"节点本身"几乎没内容——它代表的是"走到这里所拼出的那个前缀"。深度 = 前缀长度。

根 →c→ →a→ →r→ 这条路

拼出前缀 "car"

② 孩子按字符索引（child[26]）

一句话：每个节点有 26 个孩子位对应 a~z；第 c='x'-'a' 个位放"下一个字符是 x"的孩子，空位(NULL)=没这个分支。

查"下一个字符走哪"是 O(1) 数组索引，不用比较。字符集大就用 26→更大数组或哈希。

'a'-'a'=0 'd'-'a'=3

child[3] 就是 "d" 那个孩子

③ isEnd 区分"单词 vs 前缀"

一句话：同一个节点，可能既是一个完整单词、又是别的词的前缀（如 car 是 card 的前缀，自己也是词）。只有 isEnd=true 才算"存过的单词"。

查找走到末尾节点后，必须再看 isEnd——能走通只代表"是前缀"。漏看它就是最经典的 bug。

查 "ca"：能走到 a，但 isEnd=false

⟹ 只是前缀，不是单词

④ 共享前缀 → 省空间、查得快

一句话：相同开头只存一份；查或插一个长度 L 的词只走 L 步，跟字典里已有多少词无关。

查找/插入都是 O(L)（L=词长），不像哈希要算整串、也不会因词多而变慢。代价：每节点 26 个指针，稀疏时费内存。

car / card / cat → "ca" 只画一次

插 "care"：复用 car，只加 1 个节点

4 错误实验室 · 点一下亲眼看 bug

下面 4 个是写 Trie 最常翻车的坑——第 ① 个「漏查 isEnd」正是考试爱挖的「前缀误识别」。点击卡片，控制台会模拟运行效果。

① 查找末尾直接 return true

漏看 isEnd → 把前缀 "ca" 误判成已存单词

② 新节点 isEnd 没置 false

malloc 的垃圾值当真 → 一堆前缀莫名变"单词"

③ 字符没减 'a' 当下标

用 s[i]（=97…）直接索引 child[26] → 越界

④ 插入时忘标终止

没写 cur->isEnd=true → 刚插入的词查不到

// 点击上方任一卡片，查看错误代码与运行效果

$ ./a.out （等待运行...）

5 即时小测 · 5 题 + 动手例题

这 5 题都卡在初学者最常错的点上——词数怎么数、前缀≠单词、插入新增几个节点、字符下标、为什么必须查 isEnd。最后到练习系统亲手写一遍 search。

去做例题：Trie · 是不是一个已存单词

去做例题

读完这节，你应该明白：

Trie 把"一堆字符串"摊成一棵树：每条边一个字符，从根走下来的路径就是字符串，节点本身不存整串。靠 child[26]（按 s[i]-'a' 索引）做到"下一个字符走哪"是 O(1)；靠 共享前缀省空间、让查/插稳定 O(L)（与词数无关）。最关键、也最容易错的一条：能走通只说明它是某些词的前缀，必须看终点的 isEnd 才能断定"是不是一个已存单词"——漏查 isEnd 就是经典的"前缀误识别"。考试爱考数词数（=isEnd 节点数）、查找路径、插入新增节点数。它常用来做自动补全，也是除哈希表外存"键"的另一条路 ↓

字典树 (Trie)

字典树 Trie