前缀树

像这样一颗简朴的树。

他就能代表好几个字符串

由a开头的

ak、as、ab、abe、abc、abct、abcd、abcde........

因为很多前缀字符都是重复使用的，所以在保存大量字符串时，可以节约内存。

public static class TrieNode { public int path; public int end; public TrieNode[] map; public TrieNode() { path = 0; end = 0; map = new TrieNode[26]; } }

TreeNode表示每个节点的属性，

path代表这个字符使用过几次，

end该节点代表某个字符串的最后一个节点，充当了几次，比如上面的树，c这个节点，他充当了ab、abc的结束节点。所以他的end应该是2。

根据这些属性我们可以做到

  第一：词频统计。统计某个单词出现的次数,,(end)

 第二：查找所有前缀一样的单词，或者单词数量

package basic_class_05; public class TrieTree { public static class TrieNode { public int path; public int end; public TrieNode[] map; public TrieNode() { path = 0; end = 0; map = new TrieNode[26];//26意思是存放可以存放26个后续节点，因为有26个英文字母 } } private TrieNode root;//定义所有链的头节点 public TrieTree(){ root = new TrieNode(); } public void insert(String word) {//添加一个字符串 if(word==null){ return; } char[] chs = word.toCharArray(); TrieNode node = root;//指向头节点 int index=0; for(int i=0;i<chs.length;i++){ index = chs[i]-'a';//计算ascll码，26个位置。0代表'a'、1代表'b''''''' if(node.map[index]==null){//如果还没有创建过这个节点。 node.map[index]= new TrieNode(); } node = node.map[index]; node.path++;//路过这个节点一次 } //已经插入完毕。 //node已经指向最后一个字符 node.end++; } public boolean search(String word) {//判断树中有没有该字符串 if (word == null) { return false; } char[] chs = word.toCharArray(); TrieNode node = root; int index =0; for(int i=0;i<chs.length;i++){ index = chs[i]-'a'; if(node.map[index]==null){ return false; } node = node.map[index]; } return node.end!=0; } public void delete(String word) {//删除一个字符串 if(word==null){ return; } if(search(word)){//判断是否存在该字符串 char[] chs = word.toCharArray(); TrieNode node = root; int index = 0; for(int i=0;i<chs.length;i++){ index = chs[i]-'a'; if(node.map[index].path--==1){ node.map[index] =null; return; } node = node.map[index]; } node.end--; } } public static void main(String[] args){ TrieTree trie = new TrieTree(); System.out.println(trie.search("zuo")); trie.insert("zuo"); System.out.println(trie.search("zuo")); trie.delete("zuo"); System.out.println(trie.search("zuo")); trie.insert("zuo"); trie.insert("zuo"); trie.delete("zuo"); System.out.println(trie.search("zuo")); trie.delete("zuo"); System.out.println(trie.search("zuo")); trie.insert("zuoa"); trie.insert("zuoac"); trie.insert("zuoab"); trie.insert("zuoad"); trie.delete("zuoa"); System.out.println(trie.search("zuoa")); } }