Java 数据结构与算法中的字典树，你学会了吗？

字典树 Trie 这个词来自于 retrieval，于 1912 年，Axel Thue 首次抽象地描述了一组字符串数据结构的存放方式为 Trie 的想法。这个想法于 1960 年由 Edward Fredkin 独立描述，并创造了 Trie 一词。你看看，多少程序员为了一个词、方法名、属性名，想破脑袋！,在计算机科学中，字典树(Trie)也被称为”单词查找树“或”数字树“，有时候也被称为基数树或前缀树（因为可以通过前缀的方式进行索引）。—— 它是一种搜索树，一种已排序的数据结构，通常用于存储动态集或键为字符串的关联数组。,与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。,,字典树字母的存放有26个，也就是说在实现的过程中，每一个节点的分支都有26个槽位用来存放可能出现的字母组合。同理如果是数字树的话就是10个数字的组合，每个字典树上的节点对应的分支则有10个操作存放可能出现组合的数字。,接下来我们就基于 Java 语言实现一个字典树的存放和遍历索引的功能。,字典的树的节点需要包括此节点内嵌的关联节点，之后是节点的字母、到此字母是否为单词、单词的前缀、单词字符串和当前单词的非必要注释。,,insert 方法接收单词和注释信息，并对一个单词按照 char 进行拆分，拆分后则计算出索引位置并以此存放。存放完成后标记单词和附属上单词的注释信息。,,从字典树从检索元素的过程分为2部分，第1部分是根据提供的索引前缀精准匹配到单词信息，第2部分是根据索引前缀的最后一个单词开始，循环递归遍历从当前位置所能关联到的字母直至判断为是单词标记为结束，通过这样的方式把所有匹配动的单词索引出来。,list.size() >= 15 是判定索引的最大长度，超过这个数量就停止索引了，毕竟这是一种O(n)时间复杂度的操作，如果加载数十万单词进行匹配，执行速度还是比较耗时的。,这里提供一些有相近字母的单词和名词，用于测试。你也可以尝试读取txt文件，检索存入数十万单词进行检索验证。,通过测试结果可以看到，把所有以ba开头的单词全部检索出来了。这也是字典树最核心功能的体现。,读者在学习的过程中，可以尝试在检索的方法体内打一些断点看一下具体的执行过程，方便学习整个执行步骤。