前缀树

前缀树的概念

Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较。

Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

前缀树的基本性质

根节点不包含字符，除根节点外每一个节点都只包含一个字符。
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点包含的字符都不相同。通过前缀树的性质，我们可以清楚的明白前缀树的根本是利用路径去表达某个单词是否在树中。

通过图片我们可以看到一条路径下是由多个字符所组成，那么想要在树中表示出某个单词，就需要对某个单词结束的字母进行一个标志。如下图：

代码实现

首先我们来分析一下树的节点构成：

  class Node1 {
        public boolean end;
        public Node1[] nexts;

        public Node1() {
            end = false;
            nexts = new Node1[26];//代表26个字符
        }
    }

end：用于标识该节点是否是单词结束的节点

nexts：用于表示当前节点（字符）的下一个节点（字符）所在位置（要理解节点只是占位，路径才是存储）

(ps:还可以根据具体需求添加节点构成，例如：节点结束次数)

下面来看我们的整体代码：

class Trie {
    // 前缀树节点类型
    class Node1 {
        public boolean end;
        public Node1[] nexts;

        public Node1() {
            end = false;
            nexts = new Node1[26];
        }
    }
    private Node1 root;
    public Trie() {
        root = new Node1();
    }

    //向前缀树中插入单词
    public void insert(String word) {
        if(word==null){
            return;
        }
        char[] chs = word.toCharArray();
        Node1 node = root;
        int index = 0;
        //遍历字符串由字符对应节点数组的某个位置形成一条路径
        for (int i = 0; i < chs.length; i++) {
            // 由字符，对应成走向哪条路
            index = chs[i] - 'a';
            //当前节点的next数组中该位置为空的话
            if (node.nexts[index] == null) {
                //生成节点占位
                node.nexts[index] = new Node1();
            }
            node = node.nexts[index];
        }
        node.end=true;
    }

    //判断前缀树中是否有某个单词
    public boolean search(String word) {
        if (word == null) {
            return false;
        }
        char[] chs = word.toCharArray();
        Node1 node = root;
        int index = 0;
        for (int i = 0; i < chs.length; i++) {
            // 由字符，对应成走向哪条路
            index = chs[i] - 'a';
            //当前节点的next数组中该位置为空，表示当前树对应路径中无该字符
            if (node.nexts[index] == null) {
                return false;
            }
            //继续往下走
            node = node.nexts[index];
        }
        return node.end;
    }

    //判断前缀树中是否有前缀
    public boolean startsWith(String prefix) {
        if (prefix == null) {
            return false;
        }
        char[] chs = prefix.toCharArray();
        Node1 node = root;
        int index = 0;
        for (int i = 0; i < chs.length; i++) {
            index = chs[i] - 'a';
            if (node.nexts[index] == null) {
                return false;
            }
            node = node.nexts[index];
        }
        return true;
    }
}