数据结构——Trie

• 什么是Trie
• • 选取存储下一字符的数据结构
• 字典树的基础
• 向Trie中添加单词
• 查询Trie中的单词

Trie的数据存储方式如图：

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

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

        private class Node{
    	   public boolean isWord;
    	   public TreeMap 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;
       }

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

//向字典树中添加单词
       public void add(String word) {
    	   //从根节点开始添加单词
    	   Node cur=root;
    	   //遍历单词中的字母来添加单词
    	   for(int i=0;i 
查询Trie中的单词 
和向Trie中添加字母一样，一个结点一个结点的判断每个结点是否存在对应的映射，即可判断Trie中是否存在我们所存储的单词。
 注：在判断完最后一个字符时，注意检查该结点是否为单词末尾，以免判断错误（如panda包含了pan）
 
   //向Trie中添加一个新单词word
       public boolean contains(String word) {
    	   Node cur=root;
    	   for(int i=0;i