学习使用字典树（JAVA）

    字典树　又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。

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


如用 ak ab ab ai oricon orish 所构造出来的字典树为：


例： POJ2001，题目大意：
   给你很多个字符串，让你找每个字符串的最短前缀，但这么多字符串前缀不能有相同的，要能唯一标识一个字符串，而且前缀长度尽量小。

样例：
Sample Input

carbohydrate
cart
carburetor
caramel
caribou
carbonic
cartilage
carbon
carriage
carton
car
carbonate

Sample Output

carbohydrate carboh
cart cart
carburetor carbu
caramel cara
caribou cari
carbonic carboni
cartilage carti
carbon carbon
carriage carr
carton carto
car car
carbonate carbona

AC 代码：

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;

public class Main{
    private int SIZE = 26;
    private TrieNode root;  //字典树的根
    private List<String> l=new ArrayList<String>();
   
  
    public Main() {  //初始化字典树
         root = new TrieNode();   
    
    }  
  
    private class TrieNode {  //字典树节点
        private int num;//有多少字符通过这个节点.  
        private TrieNode[] son;// 所有的儿子节点
        private boolean isEnd;//是不是最后一个节点
        private char val;// 节点的值 
        
  
        TrieNode() {  
            num = 1; 
            son = new TrieNode[SIZE];  
            isEnd = false;  
           
        }  
    }  
  
    public void insert(String str) {  //在字典树中插入一个单词
        if (str == null || str.length() == 0) {  
            return;
        }  
        TrieNode node = root;  
        char[] letters=str.toCharArray();  
        for (int i = 0, len = str.length(); i < len; i++) {  
            int pos = letters[i] - 'a';  
            if (node.son[pos] == null) {  
                node.son[pos] = new TrieNode();  
                node.son[pos].val = letters[i];  
            } else {  
                node.son[pos].num++; 
            }  
            node = node.son[pos];  
        }  
        node.isEnd = true;  
    }  
  
      // 在字典树中查找.  
    public void search(String str) {  
        if (str == null || str.length() == 0) {  
            return ;  
        }  
        TrieNode node = root;  
        char[] letters=str.toCharArray();  
        for (int i = 0, len = str.length(); i < len; i++) {  
            int pos = letters[i] - 'a';  
            System.out.printf("%c",letters[i]);
            node=node.son[pos];
            if( node.num==1)
              break;; 
        }
    }  

   
    private void go() {
        
    Scanner in = new Scanner(System.in); 
        String s=null;
        int num=0;      
         while(in.hasNext()){
         
          s=in.next();
          l.add(s);
          insert(s);  
           num ++;
        }
   
       
        for(int i = 0; i < num; i++){  
          System.out.printf("%s ",l.get(i));  
          search(l.get(i));  
          System.out.println();  
       } 
    
  }  
      
    public static void main(String[] args) {  
      
        Main ma=new Main();
        ma.go();
          
    }  
}  

后记：
  题目虽然在北大PKU上AC了（说明解答没有错），但在自己电脑上DOS下运行时不能输出答案，问题在下面这段代码：（不然跳出循环）

 Scanner in = new Scanner(System.in); 
        String s=null;
        int num=0;      
         while(in.hasNext()){
         
          s=in.next();
          l.add(s);
          insert(s);  
           num ++;
        }

网上也没有找到答案，到底如何处理本题的输入，请各位提出，谢谢！

评论

2 楼 quanminy 2012-12-23  

  int pos = letters[i] - 'a';     这样得到的指针位置不保险，输入数字或大写字符或其他字符程序直接挂调。

1 楼 quanminy 2012-12-23  

Java代码 
Scanner in = new Scanner(System.in);  
       String s=null; 
       int num=0;       
        while(in.hasNext()){ 
         
         s=in.next(); 
         l.add(s); 
         insert(s);   
          num ++; 
       } 


这个 部分是因为Scanner 不断的等待前台输入数据，所以会不断的循环。可以设置一些特殊的字符作为命令入口，结束循环。