根节点为root

private Vertex root = new Vertex();

节点类：Vertex 

节点包含3个属性：

        protected int words; // 单词个数  到该节点为止，可以组合出单词的个数 

        protected int prefixes; // 前缀个数  到该节点位置，可以组合出符合该前缀单词的个数         protected Vertex[] edges; // 子节点  

新建英文字典树：添加单词

root 节点：

先判定word的length 是否未0 ，0 代表解表截止 words++;不需要添加子节点，前缀个数也无需增加

至多可以有26个节点 0 25 第一个单词的第一位的char(不区分大小写)-a的hash就是就是该字符的index  edges[index]

    private void addWord(Vertex vertex, String word) { //添加单词到目录树，root , word

        if (word.length() == 0) { // if all characters of the word has been                                     // added             vertex.words++;         } else {             vertex.prefixes++;//前缀个数             char c = word.charAt(0);             c = Character.toLowerCase(c);//无视大小写             int index = c - 'a';获得该节点的index             if (vertex.edges[index] == null) { // if the edge does NOT exist  新建一个                   vertex.edges[index] = new Vertex();             }               addWord(vertex.edges[index], word.substring(1)); // go the the next继续添加下个字符的节点                                                                 // character         }     }

添加完所有单词 字典树已经建好了

 

那么就是查找符合该前缀的单词数了！！

 

    /**      * 计算指定前缀单词的个数      *       * prefix      *      */     public int countPrefixes(String prefix) {//输入要查找的单词         return countPrefixes(root, prefix);  //从根节点开始查找     }       private int countPrefixes(Vertex vertex, String prefixSegment) {         if (prefixSegment.length() == 0) { // 输入的单词未空的话直接返回所有的root下的单词数 

    //或者已经到这个单词的结尾时 可以返回该节点下的子节点个数 也就是符合该前缀的单词数

                                                         return vertex.prefixes;         }           char c = prefixSegment.charAt(0); //获得第一个字符的hash         int index = c - 'a';//获得第一个字符的index         if (vertex.edges[index] == null) { // 如果该节点下无子节点 直接返回0             return 0;   //第一执行这个方法会进入          } else {               return countPrefixes(vertex.edges[index],                     prefixSegment.substring(1)); //递归           }       }  这样你就可以得到符合该前缀的所有单词的个数啦！！