哈夫曼编码小结

哈夫曼树
哈夫曼树是一最优二叉树，假设有n个字节点Tn{T1,T2,……,Tn}的权值分别为
Wn{W1,W2，……,Wn},其构造方法
step1：想找出里面权值最小的两个节点，作为新建父节点的左右子树，父节点的权值step2：为这两个子节点的权值之和在Tn中将父节点的左右子树删除，并将父节点加进step3：重复1、2步，直到Tn只剩一个节点为止。
哈夫曼编码：当建好树后，从根开始，每层左子树标记为0，右子树标记为1，按此规律索引到叶节点，此顺序的01串即为该叶节点对应的哈夫曼编码。
下面是我的建树和打印哈夫曼编码过程（实现了简单的解码）：

public class HalfmanTree {
	//key字符为value为字符的哈夫曼编码的map队列
	HashMap<String, String> map_pre= new HashMap<String, String>();
	//key字符为哈夫曼编码为字符的value的map队列，解码用的
	HashMap<String, String> map_dis= new HashMap<String, String>();
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		//String str="abbcccddddeeeee";
		//手动输入字符串
		Scanner sc=new Scanner(System.in);
		String str=sc.nextLine();
		//创建一个哈夫曼类
		HalfmanTree half=new HalfmanTree();
		//把字符串按不同字符统计权值，并存储到结点类数组中
		TreeNode [] arraynode=half.countstr(str);
		//根据结点类数组建立树
		TreeNode n=half.settree(arraynode);
		//打印叶节点中字符的哈夫曼编码，并已将编码放入map中
		half.print_hfm(n, "");
		
		//打印字符串的哈夫曼编码
		half.print_01(str);
		//打印解码的map
		half.print_map_dis();
		//打印解码后的字符串
		//System.out.println(half.discover_code("000 001	001	01	01	01	10	10	10	10	11	11	11	11	11"));
		
				
	} //主函数结束
	
	//以树节点中的权值大小为标准的比较器
	Comparator<TreeNode> com=new Comparator<TreeNode>() {
		@Override
		public int compare(TreeNode o1, TreeNode o2) {
			// TODO Auto-generated method stub
			if(o1.date>o2.date){
				return 1;
			}
			else
				return -1;
		}
	};
	
	//对字符串进行遍历，以各不同字符及对应权值创建结点类，保存到数组中返回
	public TreeNode [] countstr(String str){
		boolean flag_ever;//字符串重复标志
		//把第一个字符存入结点类队列的第一个
		ArrayList<TreeNode> listnode=new ArrayList<TreeNode>();	
		
		TreeNode node =new TreeNode();
		node.c=str.charAt(0);
		node.date=1;
	 	listnode.add(node);

		//从第二个开始遍历字符串
		for(int i=1;i<str.length();i++){
			flag_ever=false;
			//得到第i个字符
			char c=str.charAt(i);
			//遍历结点类队列
			for(int j=0;j<listnode.size();j++){
				//如果这个字符存在某个结点类中
				if(c==listnode.get(j).c){
					//把该几点权值计数加1
					listnode.get(j).date++;
					flag_ever=true;
					//结束循环
					break;
				}
			}
			//如果重复标志还是false,则表示没有重复的
			if(flag_ever==false){
				//那么应该新建一个节点，加入队列中
				TreeNode newnode =new TreeNode();
				newnode.c=c;
				newnode.date=1;
			 	listnode.add(newnode);
			 	//System.out.println(listnode.size());
			}
		}
		
		//将节点类队列的节点存到数组中
		TreeNode [] arraynode=new TreeNode[listnode.size()];
		for(int i=0;i<arraynode.length;i++){
			arraynode[i]=listnode.get(i);
//			System.out.println(listnode.get(i).c);
//			System.out.println(listnode.get(i).date);
		}
		
		return arraynode;
	}
	
	
	//由结点类数组创建一个树，返回根节点
	public TreeNode settree(TreeNode node_array[]){
		//直到只有一个节点时结束
		while(node_array.length>1){
			//对数组进行排序，按照com比较器
			Arrays.sort(node_array, com);
			//由最小两个数的所在节点创建父节点
			TreeNode node=new TreeNode();
			node.left=node_array[0];
			node.right=node_array[1];
			node.date=node_array[0].date+node_array[1].date;
			//创建新节点数组，长度减一
			TreeNode[] newnode_array=new TreeNode[node_array.length-1];
			for(int i=2;i<node_array.length;i++){
				newnode_array[i-2]=node_array[i];
			}
			newnode_array[node_array.length-2]=node;
			//把新节点数组首地址赋给院节点数组
			node_array = newnode_array;
		}
		//最后一个节点即根节点，赋哈夫曼编码，并返回根节点
		node_array[0].s="";
		return node_array[0];
	}
	
	//打印二叉树编码
	public void print_hfm(TreeNode node,String  code){
		//有节点存在时
		if(node!=null){
			
//			if(node.left ==null && node.right==null){
//			System.out.println(node.c+"的哈夫曼编码为："+code);
//	
//			}
//			print_hfm(node.left, code+"0");
//			print_hfm(node.right, code+"1");
			//该节点为叶子节点时
			if(node.left ==null && node.right==null){
				System.out.println(node.c+"的哈夫曼编码为："+node.s+" 权数为："+node.date);
				map_pre.put(""+node.c, node.s);
				map_dis.put(node.s,""+node.c);
				
			}
			//左子树为空时，打印哈夫曼编码
			if(node.left!=null){
				node.left.s=node.s+"0";
				print_hfm(node.left,node.left.s);
			}
			//右子树为空时，打印哈夫曼编码
			if(node.right!=null){
				node.right.s= node.s+"1";
				print_hfm(node.right,node.right.s);
			}
			
		}
		
	}
	//按字符输出哈夫曼编码
	public void print_01(String str){
		System.out .println(str+"各字符对应编码为：");
		for(int i=0;i<str.length();i++){
			char ch= str.charAt(i);
			String code=map_pre.get(""+ch);
			System.out.print(code+'\t');//每个编码直接加tab键间隔
		}
		System.out .println();
	}
//测试打印map_dis
	public void print_map_dis (){
		Set<Entry<String, String>> entry=map_dis.entrySet();
		for(Entry<String, String> en : entry ){
			System.out.println("键"+en.getKey()+"的值为："+en.getValue());
		}
	}
	//解码
	public String discover_code(String str_str){
		//String str="000001";
		String discode="";
		Set<String> set=map_dis.keySet();
		String s="";
		for(int i=0;i<str_str.length();i++){
			if(str_str.charAt(i)!='\t'&&str_str.charAt(i)!=' '){
				System.out.println(i);
				s=s+str_str.charAt(i);
				for(String ss :set){
					if(s.equals(ss)){
						discode=discode+map_dis.get(s);
						s="";
						break;
					}
				}
			}
			
		}
		return discode;
	}
	
}

这只是个简单的给哈夫曼树编码，应用的话可以做个解约软件，有待突破！！！！