字典树练习 POJ 1056

   Trie树提供给了一种能够在字符串的长度n时间内判断出来是否在已有集合中已经存在这个字符串了。POJ 1056是判断前缀码的问题。如果所有字符串都不是其他的字符串的前缀的话，那么就是可以直接编码的。

POJ 1056题目大意：
   给你几个二进制代码，如果有其中一个代码是另一个的前缀，输出is not immediately decodable，反之，输出immediately decodable。

样例：
Sample Input

01
10
0010
0000
9
01
10
010
0000
9

Sample Output

Set 1 is immediately decodable
Set 2 is not immediately decodable

import java.util.Scanner;
class Trie{
    class Node{//字典树节点
        Node nxt[]=new Node[10];//儿子节点
        boolean end=false;//是否是一个二进制代码的最后一个节点
        int count=0;//此节点上通过的字符(数字)个数
    }

    Node head=null;//字典树的根节点

     void clear(){
       head=new Node();
   }
    boolean insert(String str){//构造字典树
        Node p=head;
        for(int i=0;i< str.length();i++){
            p.count++;
            if(p.end) return false;//存在前缀
            if(p.nxt[str.charAt(i)-'0']==null)
                p.nxt[str.charAt(i)-'0']=new Node();
            p=p.nxt[str.charAt(i)-'0'];
        }
        p.count++;
        if(p.count>1) return false;//存在前缀
        p.end=true;
       return true;
    }
    
}
public class Main {

 
    public static void main(String[] args) {
        Trie tree=new Trie();
        Scanner in=new Scanner(System.in);
        int count=0;
        while(in.hasNext())
        {
             String s = in.next();  
             count++;  
             tree.clear();  
             int  flag=0;
            while (!s.equals("9")) {  
                if(!tree.insert(s)) flag++;  
                s = in.next();  
            }  
           if (flag!=0) {// 如果存在前缀，输出
              System.out.println("Set "+count+" is not immediately decodable");                          
            }  
            else {// 如果不存在前缀，输出   
             System.out.println("Set " +count+" is immediately decodable");  
            }  
        }  
    }
}

源码下载：