java 树 数据结构,字符树 数据结构
一、引论Trie的历史词典树Trie这个词来源于retrieval(Trie)，也叫“词检索树”或“数树”，有时也叫基树或前缀树(因为可以用前缀索引)。3354它是一个搜索树，一个有序的数据结构，通常用来存储动态集或者键是字符串的关联数组。
与二叉查找树不同，键不直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有后代都有相同的前缀，也就是这个节点对应的字符串，而根节点对应的是一个空字符串。一般不是所有节点都有对应的值，只有叶子节点和一些内部节点对应的键才有相关的值。
这是把battle的单词串按照字母拆分成字典树进行存储的示意图。键标在节点中，值标在节点下。每个完整的英语单词对应一个特定的整数。即对应于26个字母的ASCII转换值。第三，字典树结构实现了字典树中存储了26个字母，也就是说，在实现的过程中，节点的每个分支都有26个槽用于存储可能的字母组合。同理，如果是数树，就是10个数的组合，字典树中每个节点对应的分支有10个操作来存储可能组合的数。
接下来，我们将实现一个基于Java语言的字典树存储和索引遍历功能。
1\.分支节点预处理程序new ，等宽；颜色：rgb(68，68，68)；边框-半径：4px显示：块；边距：0px 0px 1.5em字体大小：14px行高：1.5厘米；断字：全断；溢出-换行：断字；空白：pre背景色：rgb(246，246，246)；边框：无；溢出-x:auto；字体样式：正常；字体-变体-连字：正常；字体-变体-大写：正常；字体粗细：400；字母间距：正常；孤儿：2名；文本对齐：开始；文本缩进：0px文本转换：无；寡妇：2名；字间距：0px-WebKit-text-stroke-width:0px；文字-装饰-粗细：初始；文字-装饰-风格：初始；text-decoration-color:initial；公共类TrieNode {
/* *形成一条链*/
public TrieNode[]slot=new TrieNode[26]；
/* *字母*/
公共char c；
/* *单词：数量0表示一个单词*/
public boolean isWord
/* *前缀*/
public int前缀；
/* * Word:特定的字符串*/
公共字符串字；
/* *解释：词语注释*/
公共字符串解释；
}字典树的节点需要包含嵌入在这个节点中的关联节点，后面是节点的字母，字母是否是单词，单词的前缀，单词串以及当前单词不必要的注释。
2\.插入元素
public void insert(字符串单词，字符串解释){
TrieNode root=wordsTree
char[]chars=words . tochararray()；
for (char c : chars) {
int idx=c- a ；//-a从0开始，参考ASCII代码表。
if (root.slot[idx]==null) {
root . slot[idx]=new TrieNode()；
}
root=root . slot[idx]；
root.c=c
root .前缀；
}
root.explain=explain//标注单词的描述信息
root . is word=true；//松散反汇编单词，并做好标记。
}insert方法接收单词和注释信息，并根据char拆分一个单词。分割后，计算并存储索引位置。完成后保存标记词和附加词的注释信息。
3\.索引元素
公用列表字符串搜索前缀(字符串前缀){
TrieNode root=wordsTree
char[]chars=prefix . tochararray()；
StringBuilder cache=new StringBuilder()；
//精确匹配：根据前面的精确搜索。
for (char c : chars) {
int idx=c- a ；
//匹配项为空。
if(idx root . slot . length idx 0 root . slot[idx]==null){
返回collections . empty list()；
}
cache . append(c)；
root=root . slot[idx]；
}
//模糊匹配：根据前缀的最后一个单词递归遍历所有单词
ArrayList String list=new ArrayList()；
if (root.prefix！=0) {
for(int I=0；I root . slot . length；i ) {
if (root.slot[i]！=null) {
char c=(char)(I a )；
collect(root.slot[i]，String.valueOf(cache) c，list，15)；
if (list.size()=15) {
退货单；
}
}
}
}
退货单；
}
受保护的void collect(TrieNode trieNode，String pre，List String queue，int resultLimit) {
//找到单词
if (trieNode.isWord) {
trieNode.word=pre
//将检索到的字保存到队列中
queue . add(trienode . word - trienode . explain)；
if (queue.size()=resultLimit) {
返回；
}
}
//递归调用以查找单词
for(int I=0；I trienode . slot . length；i ) {
char c=(char)( a I)；
if (trieNode.slot[i]！=null) {
collect(trieNode.slot[i]，pre c，queue，result limit)；
}
}
}从字典树中搜索元素的过程分为两部分。第一部分是根据提供的索引前缀精确匹配单词信息，第二部分是从索引前缀的最后一个单词开始，从当前位置开始递归遍历可关联的字母，直到判断该单词为结尾，这样所有匹配的单词都被索引。
List.size()=15是判断索引的最大长度。如果超过这个数字，索引将会停止。毕竟这是一个时间复杂度为O(n)的运算。如果加载几十万字进行匹配，执行速度还是比较耗时的。
四。字典树函数测试@Test
public void test_trie() {
Trie Trie=new Trie()；
//存款
Trie.insert(bat ，大昌)；
Trie.insert(batch ， batch )；
Trie.insert(母狗，拼图)；
Trie.insert(battle ， battle )；
logger . info(trie . tostring())；
//检索
列表字符串trie nodes=trie . search prefix( ba )；
Logger.info(测试结果：{} ，JSON . tojsonstring(trienodes))；
}下面是一些字母相近的单词和名词，供测试。也可以尝试读取txt文件，搜索并存储几十万字进行搜索验证。
测试结果06:21:38.226[主]信息系统。_ _测试_ _。trie测试-测试结果：[ bat-大厂， batch-batch ， battle-battle]
从测试结果可以看出，以ba开头的词都被检索到了。这也是字典树核心功能的体现。
在学习的过程中，读者可以尝试在检索方法中制作一些断点来查看具体的执行过程，以便于学习整个执行步骤。
版权归作者所有：原创作品来自博主小二上九8，转载请联系作者取得转载授权，否则将追究法律责任。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。