Part one【何谓字典树】
又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
字典树与字典很相似,当你要查一个单词是不是在字典树中,首先看单词的第一个字母是不是在字典的第一层,如果不在,说明字典树里没有该单词,如果在就在该字母的孩子节点里找是不是有单词的第二个字母,没有说明没有该单词,有的话用同样的方法继续查找.字典树不仅可以用来储存字母,也可以储存数字等其它数据。
比如我们创建一个字典树包含下列单词：
inn, int, at, age, adv, ant
是不是非常的类似于新华字典的拼音查词的顺序啊，比如查“生”就要从sh声母开始找e再找n再找g。
Part two【字典树的数据结构】
专门以小写字母为例，可以用数据结构为：
简单版本：
Part three【字典树的生成】
我们需要用到字典树来对字符串进场分析的时候就要将这个字符串放进我们的字典树（就像字典收录新词一样）但是没真正像收录新词那么难。我们只需要2步。
1.定义指向根节点的指针P，和一个交换用的指针Q
2.从字符串开始下标到结束（0-len）我们依次将字符做出节点。方法是：将字母由字典序化为数字，则指针next[该字典序]指向的地方为空时我们开辟一个指针空间给Q，将其计数初始化为1。然后从0-MAXN将他next[]指向的全部初始化为NULL。再将P的next[字典序]指针指向Q,P更新为P的next[字典序]。若指针next[字典序]指向的地方已经有节点了，我们将其节点的计数++；更新P为P的NEXT。
符合简单数据结构的版本：
符合第一个数据结构的版本（分成两个函数）：
1.查找以特定字符串作为前缀的数目（符合第二个简单数据结构）
2.查找某字符串在不在字典中（符合第一个数据结构）
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/15423.html