什么是Trie

Trie的数据存储方式如图：
在这里插入图片描述

选取存储下一字符的数据结构

每个节点对应多个可能的结点，所以我们不能仅仅用链表将单词间串起来，所以我们要用TreeMap进行多结点串联

字典树的基础

这里我们以存储单词为例，其中，每个结点我们需要知道其是否存在对应字母的映射，从而判断该单词是否存在于Trie中（映射用TreeMap实现）。
除此之外，还要一个标志isWord来表明该结点是否为单词末尾结点
代码：

        private class Node{
    	   public boolean isWord;
    	   public TreeMap<Character,Node> next;
       
    	   
       public Node(boolean isWord) {
    	   this.isWord=isWord;
    	   next=new TreeMap<>();
       }
       
       public Node(){
    	   this(false);
       }
       }

几个Trie的基本功能：

private Node root;
       private int size;
       
       public Trie(){
    	   root=new Node();
    	   size=0;
       }
       
       public int getSize() {
    	   return size;
       }

向Trie中添加单词

由图示我们可以看出，结点之间通过映射关系相关联，同时通过布尔类型的isWord标志单词的末尾结点。由此，我们不难写出向Trie中添加单词的写法：

//向字典树中添加单词
       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++;
    	   }
       }

查询Trie中的单词

和向Trie中添加字母一样，一个结点一个结点的判断每个结点是否存在对应的映射，即可判断Trie中是否存在我们所存储的单词。
注：在判断完最后一个字符时，注意检查该结点是否为单词末尾，以免判断错误（如panda包含了pan）

   //向Trie中添加一个新单词word
       public boolean contains(String word) {
    	   Node cur=root;
    	   for(int i=0;i<word.length();i++) {
    		   char c=word.charAt(i);
    		   if(cur.next.get(c)==null)
    			   return false;
    		   cur=cur.next.get(c);
    	   }
    	   return cur.isWord;
       }