前缀树结构

/*实现一个前缀树*/
什么是前缀树？优点？缺点？一般用来做什么？
数据结构：
包括根节点+儿子节点

前缀树的性质：

1.每一层节点上面的值都不相同；

2.根节点不存储值；除根节点外每一个节点都只包含一个字符。

3. 如果字符的种数为n，则每个结点的出度为n，这也是空间换时间的体现，浪费了很多的空间。 
4. 插入查找的复杂度为O(n)，n为字符串长度。

典型应用是 
1. 用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。 
2. 用于前缀匹配，比如我们在搜索引擎中输入待搜索的字词时，搜索引擎会给予提示有哪些前缀。 
它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。缺点就是空间开销大。
1、前缀匹配 
2、字符串检索 
3、词频统计 
4、字符串排序
1.插入
            从树的根节点开始；定义他的子树节点；26个英文单词；
            判断根的子节点中是否包含了要插入字符串的首字符；如果有；查找字符串的下一个字符；如果没有；则新建一个节点；插入该字符串的字符。
2.查找
            从树的根节点开始；定义他的子树节点；26个英文单词；
            判断根的子节点中是否包含了要插入字符串的首字符；如果有；查找字符串的下一个字符；如果没有；返回false;
3.判断是否是前缀树
        包含两步：
        3.1：树是否是该字符串的前缀词典
        3.2: 该字符串是否是树的前缀词典

class Trie {
    //1.定义数据结构
    public class Node{
        Node[] childs=new Node[26];
        boolean isLeaf;
    }
    //2.定义根节点
    private Node root=new Node();
    
    /** Initialize your data structure here. */
    //3.空参构造器
    public Trie() {
        
    }
    //4.插入字符串
    /** Inserts a word into the trie. */
    public void insert(String word) {
         insert(word,root);
    }
    
    public void insert(String word,Node node){
        //如果根节点为空；越界；因为前缀树的根节点不为空；而且字符是从跟节点的子树开始插入
        if(node==null) return;
        //如果字符串长度为0；也归为越界条件
        if(word.length()==0){
            node.isLeaf=true;
            return;                           
        }
        //从字符串的第一个节点开始；以数组索引表示字符是否存在
        int index=isLeafIndex(word.charAt(0));
        //如果字符不存在于树结构中，新建一个树节点
        if(node.childs[index]==null){
            node.childs[index]=new Node();   
        }
        //如果存在；进行下一步判断，字符串的第二个字符开始插入；
        //前缀树的特点；同一层节点上面的两个值不相同。因此当查找到第一个字符存在时；
        //应该从当前的树节点往下插入！
        insert(word.substring(1),node.childs[index]);
    }
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
       return  search(word,root);
    }
    public boolean search(String word,Node node){
        if(node==null) return false;
        if(word.length()==0) return node.isLeaf;
        int index=isLeafIndex(word.charAt(0));
        return search( word.substring(1), node.childs[index]);
    }
    
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        return startsWith(prefix,root);
    }
    
    public boolean startsWith(String prefix, Node node){
        if(node==null) return false;
        if(prefix.length()==0) return true;
        int index=isLeafIndex(prefix.charAt(0));
        return startsWith( prefix.substring(1), node.childs[index]);
    }
    
    public int isLeafIndex(char c){
        return  c-'a';
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */