Java-前缀树

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

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

        Trie树也有它的缺点，Trie树的内存消耗非常大。

        性质：不同字符串的相同前缀只保存一份。

        操作：查找，插入，删除，查找前缀。

  前缀树的4个基本性质：

1. 根节点不包含字符，除根节点外每一个节点都只对应一个字符。

2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。

3. 每个节点的所有子节点包含的字符都不相同。

4. 每条边对应一个字母。每个节点对应一项前缀。叶节点对应最长前缀，即单词本身

        下面我们来看下前缀树结构如何定义，以及四种基本操作。首先需要明确，前缀树的节点上是不存储字符的信息的，字符信息存储在路径上。

//前缀树节点定义
public class TrieNode{
    //节点被经过几次
    public int pass;
    //节点是结尾节点次数
    public int end;
    //节点的下面节点,如果下面节点的数量范围确定，就用数组，不确定可以用其他集合比如Set
    public TrieNode[] nexts;

    public TrieNode(){
        pass=0;
        end=0;
        //假设存26个小写字母a-z 所以申请长度26的空间就够了
        nexts=new TrieNode[26];
    }
}


//前缀树结构
public class Trie{
    //根节点
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    //新增操作
    public void insert(String word){
        char[] ch=word.toCharArray();
        root.pass++;
        TrieNode cur=root;
        for(int i=0;i<ch.length;i++){
            int index=ch[i]-'a';
            if(cur.nexts[index]==null){
                //说明没有ch[i]这条路经 那就新建
                cur.nexts[index]=new TrieNode();
            }
            cur=cur.nexts[index];
            cur.pass++;
        }
        //循环结束 cur指向最后一个节点 所以其end++
        cur.end++;
    }
    
    //查找加入了几个word
    public int searchNum(String word){
        char[] ch=word.toCharArray();
        TrieNode cur=root;
        for(int i=0;i<ch.length;i++){
            int index=ch[i]-'a';
            if(cur.nexts[index]==null){
                //说明没有ch[i]这条路经 即不存在这个word
                return 0;
            }
            cur=cur.nexts[index];
        }
        return cur.end;
    }

    //删除word
    public void delete(String word){
        //先查询word是否存在
        if(search(word)==0){
            return;
        }
        char[] ch=word.toCharArray();
        TrieNode cur=root;
        for(int i=0;i<ch.length;i++){
            int index=ch[i]-'a';
            cur=cur.nexts[index];
            cur.pass--;
        }
        cur.end--;
    }

    //查找以pre为前缀的字符串有几个
    public int  searchPrefixNum(String pre){
        char[] ch=pre.toCharArray();
        TrieNode cur=root;
        for(int i=0;i<ch.length;i++){
            int index=ch[i]-'a';
            if(cur.nexts[index]==null){
                //说明没有ch[i]这条路经说明没有这个前缀
                return 0;
            }
            cur=cur.nexts[index];
        }
        return cur.pass;
    }
}

        测试结果如下

        我们举例看下前缀树长啥样。假设有b，abc，abd，bcd，abcd，efg，hii 这7个单词,那我们就会得到如下图所示的前缀树。

             ​​​​​​​        ​​​​​​​​​​​​​​、

        从图中可以清晰的看到字符串存储的情况，可以通过直接看图得出存储了哪些字符串，也可以很容易得到各种前缀字符的信息。