Go语言视频零基础入门到精通

javalearner

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

它的优点是：
   利用字符串的公共前缀来节约存储空间，最大限度的减少无谓的字符串比较，查询效率比哈希表高。

   比如说我们想储存3个单词，sky、skyline、skymoon。如果只是单纯的按照以前的字符数组存储的思路来存储的话，那么我们需要定义三个字符串数组。但是如果我们用字典树的话，只需要定义一个树就可以了。在这里我们就可以看到字典树的优势了。

它有三个基本性质:
(1)根节点不包含字符;
(2) 除根节点外每一个节点都只包含一个字符:
(3) 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串，每个节点的所有子节点包含的字符都不相同。
   
  
   
   

     
   

     
   
  


字典树的插入，删除和查找都非常简单，用一个一重循环即可。
1. 从根节点开始一次搜索
2. 取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索
3. 在相应的子树上，取得要查找关键词的第二个字母，并进一步选择对应的子树进行检索
4. 迭代过程...
5. 在某个节点处，关键词的所有字母已被取出，则读取附在该节点上的信息，即完成查找 例:
    Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).

Input
   输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串. 注意:本题只有一组测试数据,处理到文件结束.

Output
对于每个提问,给出以该字符串为前缀的单词的数量.

Sample Input
banana
band
bee
absolute
acm

ba
b
band
abc

Sample Output
2
3
1
0

代码: (字典树模板)

1. import java.util.LinkedList;  
   
2. public class Trie {     
   
3.     private int SIZE = 26;
   
4.     private TrieNode root;  //字典树的根
   
5.   
   
6.     Trie() {  //初始化字典树
   
7.         root = new TrieNode();  
   
8.     }  
   
9.   
   
10.     private class TrieNode {  //字典树节点
    
11.         private int num;//有多少单词通过这个节点,即节点字符出现的次数
    
12.         private TrieNode[] son;// 所有的儿子节点
    
13.         private boolean isEnd;//是不是最后一个节点
    
14.         private char val;// 节点的值
    
15.         
    
16.   
    
17.         TrieNode() {  
    
18.             num = 1;
    
19.             son = new TrieNode[SIZE];  
    
20.             isEnd = false;  
    
21.            
    
22.         }  
    
23.     }  
    
24.   //建立字典树
    
25.     public void insert(String str) {  //在字典树中插入一个单词
    
26.         if (str == null || str.length() == 0) {  
    
27.             return;
    
28.         }  
    
29.         TrieNode node = root;  
    
30.         char[] letters=str.toCharArray();  
    
31.         for (int i = 0, len = str.length(); i < len; i++) {  
    
32.             int pos = letters[i] - "a";  
    
33.             if (node.son[pos] == null) {  
    
34.                 node.son[pos] = new TrieNode();  
    
35.                 node.son[pos].val = letters[i];  
    
36.             } else {  
    
37.                 node.son[pos].num++;
    
38.             }  
    
39.             node = node.son[pos];  
    
40.         }  
    
41.         node.isEnd = true;  
    
42.     }  
    
43.   
    
44.      
    
45.     public int countPrefix(String prefix){  //计算单词前缀的数量
    
46.         if(prefix==null||prefix.length()==0){  
    
47.             return -1;  
    
48.         }  
    
49.         TrieNode node=root;  
    
50.         char[] letters=prefix.toCharArray();  
    
51.         for(int i=0,len=prefix.length();i< len;i++){  
    
52.             int pos=letters[i]-"a";  
    
53.             if(node.son[pos]==null){  
    
54.                 return 0;  
    
55.             }else{  
    
56.                 node=node.son[pos];  
    
57.             }  
    
58.         }  
    
59.         return node.num;  
    
60.     }  
    
61.       
    
62.     // 在字典树中查找一个完全匹配的单词.  
    
63.     public boolean has(String str) {  
    
64.         if (str == null || str.length() == 0) {  
    
65.             return false;  
    
66.         }  
    
67.         TrieNode node = root;  
    
68.         char[] letters=str.toCharArray();  
    
69.         for (int i = 0, len = str.length(); i < len; i++) {  
    
70.             int pos = letters[i] - "a";  
    
71.             if (node.son[pos] != null) {  
    
72.                 node = node.son[pos];  
    
73.             } else {  
    
74.                 return false;  
    
75.             }  
    
76.         }  
    
77.         return node.isEnd;  
    
78.     }  
    
79.   
    
80.    
    
81.     //前序遍历字典树.  
    
82.     public void preTraverse(TrieNode node){  
    
83.         if(node!=null){  
    
84.             System.out.print(node.val+"-");  
    
85.             for(TrieNode child: node.son){  
    
86.                 preTraverse(child);  
    
87.             }  
    
88.         }  
    
89.          
    
90.     }  
    
91.    
    
92.     public TrieNode getRoot(){  
    
93.         return this.root;  
    
94.     }  
    
95.       
    
96.     public static void main(String[] args) {  
    
97.         Trie tree = new Trie();  
    
98.         String[] strs={  
    
99.                 "banana",
    
100.                 "band",
     
101.                 "bee",
     
102.                 "absolute",
     
103.                 "acm",
     
104.         };
     
105.         String[] prefix={
     
106.                 "ba",
     
107.                 "b",
     
108.                 "band",
     
109.                 "abc",
     
110.         };
     
111.         for(String str : strs){  
     
112.             tree.insert(str);
     
113.         }  
     
114.         System.out.println(tree.has("abc"));  
     
115.         tree.preTraverse(tree.getRoot());  
     
116.         System.out.println();  
     
117.         //tree.printAllWords();  
     
118.         for(String pre : prefix){  
     
119.             int num=tree.countPrefix(pre);  
     
120.             System.out.println(pre+" "+num);  
     
121.         }  
     
122.          
     
123.     }  
     
124. }  

复制代码

运行:


  

  
  
   
   

     
   

     
   
  

复制代码

源码下载：http://file.javaxxz.com/2014/12/4/000757281.zip