1.前言Trie历史字典树Trie这个词来自检索。1912年，AxelThue首先抽象描述了一组字符串数据结构的存储方式，就是Trie的思想。EdwardFredkin在1960年独立描述了这个想法，创造了术语Trie。看，有多少程序员想为一个词、一个方法名、一个属性名砸破脑袋！二、字典树数据结构在计算机科学中，字典树（Trie）也被称为“单词查找树”或“数字树”，有时也被称为基数树或前缀树（因为它可以通过前缀的方式来完成）指数）。-它是一棵搜索树，一种排序的数据结构，通常用于存储动态集或键为字符串的关联数组。与二叉搜索树不同的是，键不直接存储在节点中，而是由节点在树中的位置决定。一个节点的所有后代都有相同的前缀，就是这个节点对应的字符串，根节点对应的是空字符串。一般来说，并不是所有的节点都有对应的值，只有叶子节点对应的键和一些内部节点有相关的值。这是一个将战斗词串按照字母拆分成字典树存储的图。键在节点中注释，值在节点下方注释。每个完整的英文单词对应一个特定的整数。即26个字母对应的ASCII转换值。3、词典树结构的实现词典树中存储了26个字母，也就是说在实现过程中，每个节点分支有26个槽位用于存储可能的字母组合。同理，如果是一棵数字树，就是10个数字的组合，每棵字典树上节点对应的分支有10个操作来存储可能的数字组合。接下来，我们将基于Java语言实现存储字典树和遍历索引的功能。源码地址：https://github.com/fuzhengwei/java-algorithms本章源码：https://github.com/fuzhengwei/java-algorithms/tree/main/data-structures/src/main/java/trie1.twigNodepublicclassTrieNode{/**形成一条链*/publicTrieNode[]slot=newTrieNode[26];/**字母*/publiccharc;/**单词：数字>0表示一个单词*/publicbooleanisWord;/**前缀*/publicint前缀；/**word:一个特定的单词字符串*/publicStringword;/**explanation:词的注释说明*/publicStringexplain;}字典树的节点需要包含嵌入该节点的关联节点，后面是该节点的字母，这个字母是否是一个词，单词的前缀、单词字符串和当前单词的可选注释。2.插入元素publicvoidinsert(Stringwords,Stringexplain){TrieNoderoot=wordsTree;char[]chars=words.toCharArray();for(charc:chars){intidx=c-'a';//-a从0开始，参考ASCII码表if(root.slot[idx]==null){root.slot[idx]=newTrieNode();}root=root.slot[idx];根.c=c;根前缀++；}root.explain=解释；//单词的注释解释信息root.isWord=true;//markafterloopdismandingword}insert方法接收word和comment信息，根据char拆分出一个word，计算索引位置并存储。存储完成后，存储标记的词和词所附的注释信息。3.索引元素publicList
