词典树通常称为trie树，trie树常用于搜索提示。 输入网址后，将自动搜索可能的选择。 如果没有完全匹配的搜索结果，则前缀可能最相似。
有关详细信息，请参阅维基：树
基本概念
包含8个密钥的trie结构、' a '、' to '、' tea '、' ted '、' ten '、' I '、' in '和' inn '。
image-20190428191028045
优点：最大限度地减少无谓的比较，查询效率高于散列
核心思想：在空间上改变时间，利用字符串的公共前缀降低查询时间开销达到了提高查询的目的。
缺点：空间消耗大
基本性质：
根节点不包含字符，除根节点外，每个节点只包含一个字符
从根节点到某个节点，通过路径上字符相连，是与该节点对应的字符串
每个节点的所有子节点中包含的字符都不同
实现
leet代码的第208个问题
1首先定义节点类。 因为数据结构是树，所以需要节点。
静态类三节点{
//*
*当前节点保存的字符
*/
char val；
//*
*标记当前节点是否是要保存的节点的最后一个字符的节点
*/
布尔感测；
//*
*因为存储树中的下一个节点这次只考虑小写字母
*只打开了26个数组空间
*
如果树的节点远远大于26个，则可以使用Map作为next
* TreeMap=new TreeMap () )
*/
三节点[ ]下一步=新三节点[ 26 ]；
公共树节点() {
}
公共服务(char val ) {
this.val=val；
}
}
定义树的结构。
公共类树{
//*
*树的根节点
*/
三节点根；
//*
Trie数据结构初始化
*/
公共树() }
根=新三节点(；
root.val=' '；
}
//*
在树中插入单词
*
*/
公共语音插入(字符串word ) {
三节点当前节点=根；
for(intI=0； i word.length (； I ) {
charc=word.Charat(I；
//将当前字符作为节点插入到树中
//但是在插入之前先检查
if (当前节点. next [ c-' a ' ]==null ({
current node.next [ c-' a ' ]=newtrienode (c；
}
current node=current node.next [ c-' a ' ]；
}
//现在标志来到单词的末尾
currentNode.isEnd=true；
}
//*
*判断某个单词是否在树中
*/
publicbooleansearch (字符串word ) {
三节点当前节点=根；
for(intI=0； i word.length (； I ) {
charc=word.Charat(I；
//单词还没说完，就发现已经不匹配了
if (当前节点. next [ c-' a ' ]==null ({
返回假；
}
current node=current node.next [ c-' a ' ]；
}
//每个单词的末尾都设置为true
//如果当前为false，则表示没有存储此单词
return currentNode.isEnd；
}
//*
*确定当前单词是否为Trie树种某个单词的前缀。 请注意，这里的逻辑与查询相同。 唯一不同的是
*前缀匹配后返回true
*/
公共蓝牙(string prefix ) {
三节点当前节点=根；
for(intI=0； i prefix.length (； I ) {
charc=prefix.charat(I；
if (当前节点. next [ c-' a ' ]==null ({
返回假；
}
current node=current node.next [ c-' a ' ]；
}
返回真；
}
}
3写测试代码看效果
publicstaticvoidmain (字符串[ ] args ) {
三叉树=新三叉树(；
trie.insert(flink )；
trie.insert('Netty )；
trie.insert(MySQL )；
trie.insert(redis )；
//false
system.out.println (trie.search (' MongoDB ' )；
//真
system.out.println (trie.search (' redis ' )；
//false
system.out.println (trie.search (' my ' )；
//真
system.out.println (trie.search (' MySQL ' ) )；
//真
system.out.println (trie.starts with (' my ) )；
}
4运行程序，取得了预期的结果
image-20190429081246407
最后一次
这里只是给出了树的简单介绍和实现，关于树还有很多话题。
扩展：
虽然压缩了Trie树，优化了一定的空间，但是增加了维护成本
后缀树
三分词典的树