目录
- 简介
- 工作过程
- 数据结构
- 初始化
- 构建字典树
- 应用
- 匹配有效单词
- 关键词提示
- 总结
Trie又称为前缀树或字典树，是一种有序树，它是一种专门用来处理串匹配的数据结构，用来解决一组字符中快速查找某个字符串的问题。Google搜索的关键字提示功能相信大家都不陌生，我们在输入框中进行搜索的时候，会下拉出一系列候选关键词。
上面这个关键词提示功能，底层最基本的原理就是我们今天说的数据结构：Trie树
我们先看看Tire树长什么样子，以单纯的单词匹配为例，首先它是一棵多叉树结构，根节点是一个空字符，树中节点分为普通节点和结尾节点（如图中红色节点）。结尾节点表示加上前面前缀，可以称为一个单词，如图中hi，him。
Tire树与之前串匹配最大的不同点是，之前我们都是单模式串，查看主串中是否有与模式串匹配的子串，操作过程也是用模式串去与主串进行比较。而Tire树是多模式串，我们先将模式串提前构建成Tire树，然后查看主串是否匹配模式串，且更适用于类似如上关键词提示的前缀匹配。接下来我们自己通过实现一个简易的关键词提示功能来讲解Tire树。
一个value存储当前节点值，用一个26大小的数组存储当前节点的孩子节点，这是一个简单但是可能产生浪费的方法，可以采用有序存入采用二分法查找，或者采用hash表，跳表进行优化。一个标志当前节点是否可作为尾节点。
初始化一个仅有root节点的Tire树，root节点值为'/0'。
将需要加入的模式串加入Tire树，遍历当前字符串字符，从Tire树根节点开始查找当前字符，如果字符已经存在不需要处理，并且从这个字符节点出发，查看下一个字符是否存在，如果当前节点不存Tire树，才需要插入当前字符，当插入最后一个字符时需要标志当前字符节点为尾节点。
遍历字符串，从根节点出发，查看字符是否存在，只要存在不存在的情况，直接返回false，如果每个字符都存在，判断最后一个字符是否为结尾节点，如果不是，到这里还不是一个有效单词，返回false，否则，返回true。
测试样例 运行结果
根据输入的关键词前缀，匹配所有可能出现的关键词。首先遍历字符串，从节点出发，只要有一个找不到，直接返回null，直至找到最后一个字符对应的节点，从该节点出发找到所有尾节点。
测试样例 运行结果
到这里Trie树就讲完了，主要就是聚合前缀，通过树的特性，按照链路进行访问，同时标志尾节点，标志到当前节点是一个完整的字符串。
以上就是详解Java中字典树(Trie树)的图解与实现的详细内容，更多关于Java字典树的资料请关注我们其它相关文章！
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/3993.html