一、概念复习：
1.字典树是一种高级的数据结构，传闻早前手机客户经常会因为通讯录中存储太多人，导致每次查找号码时耗时过长，这个问题被微软的一个实习生解决了，他的解决办法就是使用了字典树这种神奇的数据结构。
2.字典树的优势在于，他的查找时间取决于查询内容的长度，而不是取决于库中有多少数据量，这在一些大数据量的应用场景中十分管用。
3.他的基本结构就是在节点中存储指向下一个节点的指针，并且通过不同字符，可以找到不同的节点。
4.为了更好的使用字典树，我们采用Map<char,Node>next,来存储键值对，通过“c”找到下一个节点。
————————————————————————————————————————————
在本次数据结构部分，采用更加简洁的构造函数，如下：
public class Trie {//内部类，声明一个私有的节点，包含：isWord、next(Character,Node)private class Node{boolean isWord;TreeMap<Character,Node>next;public Node(boolean isWord){this.isWord=isWord;next=new TreeMap<>();}public Node(){this(false);}}private int size;private Node root;public Trie(){root=new Node();size=0;}其中：isWord 用于判断是否是一个单词（还是某个单词的中间部分？）
二、全部代码及注释部分
package IMUHERO;
import java.util.TreeMap;
public class Trie {//内部类，声明一个私有的节点，包含：isWord、next(Character,Node)private class Node{boolean isWord;TreeMap<Character,Node>next;public Node(boolean isWord){this.isWord=isWord;next=new TreeMap<>();}public Node(){this(false);}}private int size;private Node root;public Trie(){root=new Node();size=0;}public int getSize(){return size;}public boolean isEmpty(){return size==0;}public void add(String word){Node cur=root;for (int i=0;i<word.length();i++){char c=word.charAt(i);if (cur.next.get(c)==null){cur.next.put(c,new Node());}cur=cur.next.get(c);}if (!cur.isWord){cur.isWord=true;size++;}}//向字典树中插入元素的递归写法public void insert(String word){insert(word,0,root);}private void insert(String word,int index,Node node){if (index==word.length()&&!node.isWord){node.isWord=true;size++;}if (index==word.length())return;char c=word.charAt(index);if (node.next.get(c)==null){node.next.put(c,new Node());}insert(word,index+1,node.next.get(c));}public boolean contain(String word){Node cur=root;for (int i=0;i<word.length();i++){char c=word.charAt(i);if (cur.next.get(c)!=null){cur=cur.next.get(c);}else return false;}return cur.isWord;}//查询字典树中是否包含某个单词的递归写法public boolean cotainsII(String word){return cotainsII(word,0,root);}private boolean cotainsII(String word ,int index ,Node node){if (index==word.length())return node.isWord;char c=word.charAt(index);if (node.next.get(c)==null)return false;return cotainsII(word,index+1,node.next.get(c));}/** Returns if there is any word in the trie that starts with the given prefix. */public boolean startsWith(String prefix) {Node cur=root;for (int i=0;i<prefix.length();i++){char c=prefix.charAt(i);if (cur.next.get(c)==null){return false;}cur=cur.next.get(c);}return true;}//查询字典树中是否包含以某个字符串为前缀的单词public boolean startsWithII(String prefix){return startsWithII(prefix,0,root);}private boolean startsWithII(String prefix,int index,Node node){if (index==prefix.length())return true;char c=prefix.charAt(index);if (node.next.get(c)==null)return false;return startsWithII(prefix,index+1,node.next.get(c));}/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */查询字典树中是否包含以某个字符串为前缀的单词，其中'.'可以代替任意一种字符public boolean search(String word){return search(word,0,root);}private boolean search(String word,int index,Node node){if (index==word.length())return true;char c=word.charAt(index);if (c!='.'){if (node.next.get(c)==null)return false;return search(word,index+1,node.next.get(c));}else {for (char nextChar:node.next.keySet()){if (search(word,index+1,node.next.get(nextChar))){return true;}}return false;}}}
注：文中图片引用慕课liuyubobobo老师的课程讲解，主要目的是为了总结自己的学习历程，分享心得体会，如有转发请标注此项。