C＋树进阶系列之深度剖析字典（trie）树

1. 前文

本文和大家一起聊聊字典树，从字典二字可知，于功能而言，字典树是类似于的一棵信息树。字典树有 大特点：

有容乃大，能存储大量的数据信息。

提供有基于关键字的查询、检索机制。

常用存储字符串（单词）信息，使用能方便实现进行字符串的存储、查询、统计、排序……一系列操作。

2. 字典树特点

是树结构的典型应用，如下图所示，为一棵字典树。的叶结点起标志性作用，标记字符串的结束，类似于字符串的结束符号。

通过观察，可以大致了解字典树的几个特点：

字典树不是，字典树的每一个结点可以有多个子结点，除根结点外每个结点存储一个字符信息(常用于字符信息存储，但不仅限于字符信息)。

顺着根结点向子结点连接，可以找到一个信息。只因为这个特性，字典树如其名，可存储大量的单词。如从根结点开始，找到它的第一个子结点，然后找到的子结点，再顺着 找到。这样就能得到子符串。

具有的字符串不需要重复存储，公用共同的祖先，如和的公共祖先结点是。这也是字典树的一大特点，相比较其它的存储方案，具有高度的空间利用率。

3. 字典树的物理存储

字典树的常用有和，其它可根据应用场景的需要进行扩展。字典树的物理实现可以使用和存储 种方案，本文分别探讨这 种方案的实现过程。

3.1 链式存储

为了简化操作，实现过程中使用了的容器存储任一结点的子结点，当然，也可以使用带有头结点的链表。

3.1.1 结构类型

结点类型： 描述字典树的结点信息。

字典类： 维护字典的常用，此处先提供基本的，后面根据需要再扩展。

3.1.2  常规 3.1.2.1 函数

功能描述： 提供添加字符串（单词）的功能，是构建字典树的第一重要环节。

实现流程：现以添加字符串为例，讲解添加函数的实现过程。

首先构建根结点。根结点不需要存储具体的数据信息。

分解字符串，且读入字符，以根结点为当前结点，查询当前结点是否存在值为的子结点。

因字典树刚创建，此子结点不存在，则为根结点新建值为的子结点，并且指向新建的结点。

继续从字符串中分割出字符，检查当前结点是否存在值为的子结点。没有则为当前结点创建值为的新结点，重设当前结点的指针为新建结点。

同理，分割出，因当前结点不存在值为的子结点，为当前结点构建新结点。且重设当前结点的指针。

当字符串分割完毕后，最后添加值为的叶结点作为结束标志符。

在现有字典树上继续添加字符串（单词）。当前结点需要重置为根结点，分割字符串时，因为值为和的结点已经存在，则仅让当前结点向下滑动。

分割出字符，因当前结点不存在值为的子结点，新建值为的子结点。且因字符串已经分割完毕，为结点添加结束子结点。如下图所示。

编码实现：

实现辅助函数：

实现函数：

测试插入函数：

输出结果：

3.1.2.2 函数

功能描述： 查询给定的字符串（单词）是否存在于字典树中。

实现流程： 查询和插入流程相似。如果检查到存在与分割出来的字符值相等的子结点便继续向下查询，否则，认为查询失败。

不要求一定的是完整字符串（单词），仅是前缀也可以。

如下图所示，虽然字典树中不存在字符串（单词），因为存在前缀，也认为是存在的。

编码实现：

测试查询：

输出结果：

3.1.2.3 函数

功能描述： 返回字典树上的所有字符串（单词）。

实现流程： 对于整棵树的搜索常用的方案有和搜索。针对此需求使用搜索便能查询出树上的所有单词。

编码实现：

实现辅助函数 ：显示字典树上的所有单词。

实现函数：

测试代码：

输出结果：

3.2 矩阵存储

使用存储树结点之间的关系也是一种常见方案。

基本存储思想：

对每一个结点进行编号。

以父结点的编号为矩阵的行号，子结点的编号为列号，行与列对应的单元格中存储结点的关系描述（或值、权重）。

在存储字典树信息时，对上述的存储方案可以稍加改进一下。

如先确定根结点的编号为，但是子结点在矩阵中的列号由其对应的码决定，当然，会对其范围缩小。

对应单元格中存储字符出现的顺序编号，并以此编号为此结点的标志符号。

这个编号与字符添加顺序有关，与字符本身无关。如下图所示：

字符是字符的子结点。添加过程如下图所示。

继续完成其它结点关系的存储。

上述存储的优点：

可以把矩阵的列数限制在 之内。

查询任一结点的子结点时，可以根据字符本身所携带信息找到其存储位置。如果结点下还有字符的子结点，便能轻易知道其存储位置是 并能获取结点的编号。

编码实现：

与前文的链式存储相毕较，仅是改变了存储方式，逻辑是没有发生任何变化。

输出结果：

使用数组存储的优点：

查询所有单词时，会自动对其按字典进行排序。

实现起来较直观，易理解。

4. 字典树的应用

到些，想必对字典树有了较好的理解，下文再提供 个案例 ，带你更深入体会字典树的神奇之处。

4.1 自动补全

所谓自动补全：指只要用户输入单词前缀，则会显示所有与此前缀有关联的单词。此功能在关键字搜索应用中经常可以看到。

如果字典树中存在单词集，当用户输入时，则自动显示所有以为前缀的单词：、。

实现原理：

在字典树中查找前缀是否存在。

如果存在，以此前缀最后一个字符的结点为当前结点进行深度搜索。

编码实现：

在前文的矩阵实现方案中添加如下函数。

输出结果：

4.2  求 2 个字符串的最长公共前缀

所谓字符串的公共前缀指字符串前面相同的部分。如和的公共前缀是。与自动补全功能是相逆的操作。

基本思想：

使用字典树存储所有字符串。

两个字符串的最长公共前缀的长度即他们所在的结点的公共祖先个数，于是，问题就转化为求公共祖先问题。

在树中求解结点的公共祖先问题可以有多种方案，本文侧重于字典树的理解，仅提供下面的穷举算法。其它方案可以自行查阅相关书籍。

测试：

输出结果：

5. 总结

本文介绍了字典树的逻辑结构，并且使用链式和矩阵种方案实现了字典的物理存储。并且通过 个具有代表性的案例让大家更深入理解字典树的实际应用。