数据结构 Trie树（字典树、前缀树）-编程实验室

1.什么是Trie树

Trie树，又叫字典树、前缀树（Prefix Tree）、单词查找树或键树，是一种多叉树结构。如下图：

上图是一棵Trie树，表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。从上图可以归纳出Trie树的基本性质：

根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点包含的字符互不相同。

通常在实现的时候，会在节点结构中设置一个标志，用来标记该结点处是否构成一个单词（关键字）。

可以看出，Trie树的关键字一般都是字符串，而且Trie树把每个关键字保存在一条路径上，而不是一个结点中。另外，两个有公共前缀的关键字，在Trie树中前缀部分的路径相同，所以Trie树又叫做前缀树（Prefix Tree）。

我们可以举个例子

原字符串集合：{ abcde 、aced 、bcdf 、bcff }
插入字符串：aced 、cdaa
新字符串集合：{ abcde 、abde、aced 、bcdf 、bcff 、cdaa }

说明：图中 ※ 为字符串结束的标记。

若某结点上有标记 ※，则说明从根结点到该结点为止，每个结点表示的字符相连组成的字符串存在于集合中。
相应的，对于没有标记的结点，串联成的字符串只是原有字符串的一部分，不属于字符串集合。

2.字典树的应用场景

当我们在字典树的每⼀个结点位置，额外维护⼀些信息时，就可以做到很多事情：

查询某个单词是否出现过，并且出现⼏次；
查询有多少个单词是以某个字符串为前缀；
查询所有以某个前缀开头的单词；（这个作⽤可以⽤到输⼊法中，输⼊拼⾳的时候，可以提⽰可能的单词）

当然，除了上述作⽤以外，字典树还可以解决别的问题，后续可以在做题中体会。

3.字典树的实现

基本结构

字典树的每个节点包含：

子节点指针（通常是一个数组或映射）
一个标志位，表示从根节点到该节点的路径是否构成一个完整的单词
可能包含其他辅助信息（如词频）

这里需要理解一个非常重要的问题：怎么理解idx？

3.1. 插入 ( insert ) 操作

将字符串逐个拆分成单个字符，从第一个字符开始与 Trie 树的根结点开始的子结点比对，

若有结点具有相同的字符，则以同样的方式对比下一个字符与该结点的子结点。

举例：

在图 1 中插入字符串 abde ( 拆分：a/b/d/e)

对于字符 a ，根结点的子结点中有 a ，向后判断下一个字符 b 与结点 a 的子结点；
对于字符 b ，a 结点的子结点中有 b ，向后判断下一个字符 d 与结点 b 的子结点；
对于字符 d ，b 结点的子结点中没有 d ，因此要创建新结点 d，向后判断下一个字符 e 与结点 d 的子结点；
对于字符 e ，d 结点的子结点中没有 e ，因此要创建新结点 e

( 从创建了一个新结点起，后面剩下的字符显然都要创建新的结点，但其操作和之前的判断相同 )

举例：

在图 2 中插入字符串 cdaa ( 拆分：c/d/a/a)

对于字符 c ，根结点的子结点中没有 c ，因此要创建新结点 c，剩下的字符 daa 以相同的操作，逐个创建，以存储字符串。
注意：在插入完字符串之后，要给末尾的结点加上结束标记。

现在我们就能写出代码了，首先我们先定义好我们需要的一些数据结构。

#include <iostream> using namespace std; const int N = 100010; int son[N][26]; // 存储每个结点的所有儿子结点 // 在题目中，字符串只包含 26 个小写字母 // 因此每个结点最多只会向外连 26 条边 ( 最多只有 26 个儿子结点 ) int e[N]; // count，记录以这个结点结尾的单词有多少个 // 它在本模板中作为 字符串结束标记 int idx; // 存储当前已经使用到的结点的下标 // 下标是 0 的结点，既是根节点，又是空结点 int p[N]; //记录每个节点被经过的次数, //p[i] 表示有多少个单词的前缀经过节点 i。例如，根节点的 p[0] 等于插入的单词总数，因为所有单词都从根节点开始。

这里先回答一个问题：如何理解idx?

idx 是字典树中节点的动态分配标识符，用于唯一标记每一个新创建的节点。它的核心作用是：

唯一性：确保每个新节点有唯一的索引，避免路径冲突。
动态扩展：按需分配节点，无需预先固定树的结构。

为什么需要 idx？

字典树的本质是用节点路径表示字符串，例如字符串 "apple" 的路径是：

根节点 → a → p → p → l → e

根节点的索引固定为 0。
其他节点需要动态创建，例如：

根节点的子节点 a 可能对应索引 1。
a 的子节点 p 可能对应索引 2，依此类推。

idx 的作用就是为这些新创建的节点分配一个全局唯一的索引，确保路径的唯一性。

idx 的工作流程

初始化：程序开始时，idx = 0（根节点已存在，无需分配）。
插入字符串：

当需要创建新节点时，执行 son[cur][path] = ++idx。
++idx 会先递增 idx，再将新值赋给节点。
例如，第一个新节点的索引是 1，第二个是 2，依此类推。

具体示例

假设插入字符串 "abc"：

根节点 0：

p[0]++（根节点被经过次数+1）。
字符 'a' 对应路径 0（path = 'a'-'a' = 0）。
检查 tree[0][0]，若未创建（初始为0），则分配新节点 tree[0][0] = ++idx = 1。

节点 1：

p[1]++（经过次数+1）。
字符 'b' 对应路径 1。
检查 tree[1][1]，若未创建，分配 tree[1][1] = ++idx = 2。

节点 2：

p[2]++。
字符 'c' 对应路径 2。
检查 tree[2][2]，若未创建，分配 tree[2][2] = ++idx = 3。

结束：

1. e[3]++（标记字符串结尾）。

最终树的结构为：

根节点 (0) → a (1) → b (2) → c (3)

关键问题解答

为什么不用固定索引？

字符串的组合是无限的，无法预先确定需要多少节点。idx 按需分配，节省内存。

idx 会重复吗？

不会。idx 严格递增，每个新节点分配的索引唯一。

idx 和数组大小 N 的关系

N 需足够大（如 1e6），否则 idx 超过 N 会导致数组越界。

接下来我们就能写出这个代码

// 插入字符串到字典树 void insert(string& s) { int cur = 0; // 从根节点（索引0）开始遍历 p[cur]++; // 根节点被经过次数+1（总单词数统计） for (auto ch : s) // 遍历字符串的每个字符 { int path = ch - 'a'; // 将字符转换为路径编号（a=0, b=1...z=25） // 如果当前路径不存在，则创建新节点 if (son[cur][path] == 0) { son[cur][path] = ++idx; // 分配新节点，idx递增 } cur = son[cur][path]; // 移动到子节点 p[cur]++; // 当前节点经过次数+1 } e[cur]++; // 循环结束时，cur位于字符串末尾节点，标记单词结尾次数+1 }

3.2. 查询 ( query ) 操作

与插入操作的原理基本相同，

将需要查询的字符串逐个拆分成单个字符，逐个与 Trie 树中的结点比较，直至发现 Trie 树中不存在的字符，或要查询的字符串的各个字符都比较完成。
对于发现 Trie 树中不存在的字符，一旦发现，就能确定要查询的字符串不属于原集合。

举例：

在图 3 中查询 acwing ，
能找到 a → c ，但 c 的子结点中没有 w ，则确定集合中不存在该字符串

对于要查询的字符串的各个字符都比较完成，则存在两种情况：

① 要查询的字符的确属于集合；
② 要查询的字符是集合中某个字符串的前缀。
举例：

在图 3 中查询 ac ，能找到 a → c ，字符串比较完成。

因为 ac 是原有字符串 aced 的一部分 ( 前缀 )。
此时就需要用到结点上的字符串结束标记了。
在 ac 的查询过程中，最后判断的结点落在了结点 c 上，但该结点没有字符串结束标记，因此可以判断 ac 不属于原集合。

举例：

在图 3 中查询 aced ，最后判断的结点落在了结点 d 上，
该结点具有字符串结束标记，因此可以判断 aced 属于原集合。

查询完整字符串出现的次数

// 查询完整字符串出现次数 int find(string& s) { int cur = 0; // 从根节点开始查找 for (auto ch : s) { int path = ch - 'a'; if (son[cur][path] == 0) { return 0; // 路径不存在，说明单词不存在 } cur = son[cur][path]; // 沿路径向下移动 } return e[cur]; // 返回结尾节点的单词计数 }

查询有多少个单词以字符串s为前缀

// 查询以s为前缀的单词数量 int find_pre(string& s) { int cur = 0; for (auto ch : s) { int path = ch - 'a'; // 原代码中的get_num(ch)应为ch-'a'，否则无法编译 if (son[cur][path] == 0) { return 0; // 前缀路径不存在 } cur = son[cur][path]; } return p[cur]; // 返回该前缀最后一个节点的经过次数 }