1.Trie基础

Trie是一种树形结构，是一颗多叉树，如果我们实现树中只存储26个字母，那这颗树就是26叉树。
数据结构学习，Trie（字典树，前缀树）（java语言）
如上图，不过它的值并不是储存在树的节点中，由于使用Map（映射）结构，而且不论在新增操作还是查询操作时，我们都会提前知道所要插入/修改的单词的字母，所以将其放入Map当做Key使用。

首先定义Trie的节点结构，由于不同的单词可能有相同的前缀，所以我们增加一个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;
    }

2.添加操作

在Trie中添加一个单词，就可以从根节点开始不断判断next中是否存在单词对应索引处的字母，存在则直接移动到下一节点，不存在则先创建下一节点再移动到下一节点，最后将isWord改成ture即可。


        //向Trie中添加一个单词word
    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++;
        }
    }

3.查询操作

查询操作与新增操作大致相同，只不过在遍历单词中的字母时，如果字母不存在就直接返回false，循环结束后判断结尾处节点的isWord是否为true即可判断有无这个单词。

    //查询单词word是否在Trie中
    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;

    }

4.前缀查询

前缀查询与3中查询操作基本相同，只要将最后的返回值做一下调整，修改为true即可。（默认pan为pan的前缀）

    //查询在Tire中单词以prefix为前缀
    public boolean isPrefix(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;
    }

5.总结

Trie这种结构在查询或者新增时，与已存在的数据总量无关，只与插入或查询的单词长度有关，复杂度为O（w）----w为单词的长度。所以trie在执行查询操作时，相比其他结构，十分的高效
一种结构在一方面十分优秀的同时，必然也有缺陷，而Trie这种结构的缺点就是，占用的空间很大，因为它每一个节点都只存了一个字母。

数据结构学习，Trie（字典树，前缀树）（java语言）