字典树的概述：又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
1、字典树的构建过程
所谓字典树，就是将单词的每一个字符作为一个节点，每个节点都有一个特殊的编号，根节点不记录信息。假设我们有一个词库，里面有如下单词：【a, ab, abc, abd, ac, acd, bc, bd, c】，那么如何构建一个字典树呢？
首先有一个空节点root(根节点)：
插入第一个单词“a”的过程（a旁边的是节点编号）每个节点都有可能再衍生出26个节点（26个小写字母）：
插入单词ab的过程：
由于已经有了一个a，那我们就不需要再重新创建一个a节点，只需要在a节点后衍生b节点即可。具体实现方法是有一个二维数组ch[][], 其中ch[i][j]标识从节点i衍生出的映射值为j的字符。首先从根节点开始，根节点的编号为0，指针p指向根节点，那么ch[p]['a' - 'a']的值为1，代表从根节点出发衍生出的a节点的编号为1，由于ch[p][0]已经等于1，即a节点已经存在，那么我们将ch[p][0]赋值给指针p，那么p即为a节点的编号，由于ch[1][2]的值为0，说明a节点还未衍生出b节点，所以，我们新加入b节点，将ch[p][2]赋值为1即可。最后将p = ch[1][2]，将p指向刚刚建立的b节点，b结点为ab的结尾，那么我们cnt[2]++代表ab这个单词出现了一次。
其他单词的插入类似，在此不做过多赘述。
最后插入完成的图如下：
2、字典树的查找过程
在构建的过程中，每到一个字符串的末尾，我们用cnt[p]++，来记录该单词的频率。因此在查找的过程中，我们首先将指针p置位0，代表从根节点开始查找，然后遍历要查找单词的每个字母，将该字母按同样的方式映射到实数num，利用这个实数num判断ch[p][num]是否为1，如果为1，则说明该字母的节点存在，p指针指向该节点（p = ch[p][num]），继续遍历下一个字符，如果中间过程出现ch[p][num] = 0，直接返回0，代表不存在该单词，否则返回cnt[p](此时p已经指向查找单词的最后一个字母所在的节点)
3、完整代码如下
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/15838.html