Huffman算法

      大家在离散数学课上学过Huffman算法，我们学的时候特别不认真，对它嗤之以鼻，哭着喊着说不好学，结果现在要用java来把Huffman树编出来，也就开始郁闷了，话说这个东西也郁闷了我好久。现在给大家晒晒，我的Huffman编码的生成。有可能和您用纸画出来的编码有点不同，但是其实质都是一样的。

 

import java.util.ArrayList;

/**
 * 哈弗曼算法
 *
 */
public class Huffman {

	TreeNode treeroot;
	
	/**
	 * 能够让一个无序字符串统计出其中的字母以及出现的次数
	 * @param s 要传入的无序字符串
	 * @return 统计出含有字母以及出现次数的队列
	 */
	public ArrayList<TreeNode> getString(String s){
		ArrayList<TreeNode> str=new ArrayList<TreeNode>();
		for(int i=0;i<s.length();i++){
			char c=s.charAt(i);
			String st=""+c;
			boolean exist=false;
			for(int j=0;j<str.size();j++){
				TreeNode temp=str.get(j);
				if(temp.s.equals(st)){
					temp.times++;
					exist=true;
					break;
				}
			}
			if(!exist){
				 //在创建对象,向队列中加入之前,要先查看队中是否己有?
				 TreeNode data=new TreeNode();
				 data.times=1;
				 data.s=st;
				 str.add(data);
				 }
		}
		return str;
	}
	
	/**
	 * 冒泡排序
	 * @param MyTree 结点的队列（可以不按从小到大排列）
	 */
	public void Change(ArrayList<TreeNode> MyTree){
		
		for(int i=0;i<MyTree.size()-1;i++){
			for(int j=i+1;j<MyTree.size();j++){
				
				int itime=MyTree.get(i).times;		//前一个结点所含字母的出现次数
				int jtime=MyTree.get(j).times;		//后一个结点所含字母的出现次数
				
				if(itime>jtime){
					
					//TreeNode tag=new TreeNode();
					TreeNode temi = MyTree.get(i);
					TreeNode temj = MyTree.get(j);
					
					MyTree.set(i, temj);
					MyTree.set(j, temi);
					
//					tag=temi;
//					temi=temj;		//只改变了新设定对象的指向			
//					temj= tag;		//比较出现次数的大小 交换顺序
					
				}
				
				//把有叶片的结点放到前面
				TreeNode item=MyTree.get(i);
				TreeNode jtem=MyTree.get(j);
				
				if(item.times==jtem.times){
					if(item.LeftChild!=null&&jtem.LeftChild==null){
						MyTree.set(i, jtem);
						MyTree.set(j, item);
					}else if(item.LeftChild==null&&jtem.LeftChild!=null){
						MyTree.set(i, jtem);
						MyTree.set(j, item);
					}
				}
			}
			
		}
		
		//检测排序是否正确
//		for(int i=0;i<MyTree.size();i++){
//			System.out.println("字母为"+MyTree.get(i).s+"   出现次数为"+MyTree.get(i).times);
//			System.out.println();
//		}
	}
	
	/**
	 * 开始创建哈弗曼树
	 * @param MyTree 
	 */
	public void BuildTree(ArrayList<TreeNode> MyTree){
		
		TreeNode tn=new TreeNode();
		TreeNode node1=new TreeNode();
		TreeNode node2=new TreeNode();
		
		if(MyTree.size()>1){
			node1=MyTree.get(0);			//确定前两个最小的结点所生成的树叶
			node2=MyTree.get(1);
		
			tn.LeftChild=node1;				//确定左孩子 右孩子	
			tn.RightChild=node2;
			
			node1.root=tn;					//确定前两个孩子的根
			node2.root=tn;
			tn.times=node1.times+node2.times;//确定根值
//			tn.s="新的";
			
			MyTree.remove(0);
			MyTree.remove(0);				//移除已确定的两片树叶
			MyTree.add(tn);					//把已经确定好了的一个根添加到队列中
			
			//int ThisNum=tn.times;			//确定根的值的大小
			
//			System.out.println("左子树为"+node1.s+"  出现次数为"+node1.times+"   右子树为"+node2.s+"  出现次数为"+node2.times);
//			System.out.println();			//检测树是否创建错误
			
			Change(MyTree);					//重新排序
			BuildTree(MyTree);				//递归 再次生成树叶
			
		}else if(MyTree.size()==1){
			treeroot=MyTree.get(0);
			//System.out.println("treeroot"+treeroot.times);
			CalculateHuffman(treeroot,"");
		}

	}
	
	public void CalculateHuffman(TreeNode root,String s){
		
		if(root!=null){
//			if(root.LeftChild){
//				s+="0";
//				CalculateHuffman(root.LeftChild,s);
//			}
//			if(root.RightChild!=null){
//				s+="1";
//				CalculateHuffman(root.RightChild,s);
//因为每个结点都是有左子树和右子树的（叶片不算），故这两句话没用
//			}
			if(root.LeftChild==null&&root.RightChild==null){
				System.out.println(root.s+"编码为"+s);
				System.out.println("  出现次数为"+root.times);
			}
			CalculateHuffman(root.LeftChild,s+"0");
			CalculateHuffman(root.RightChild,s+"1");
		}
		
	}
}

 

 

 

评论

4 楼 吸血鬼猎人 2010-08-18  

沈冠军 写道

,要是能把胡哥说的那个功能给搞出来的话就厉害了啊

嗯，假懂同学貌似已经弄出来了。

3 楼 吸血鬼猎人 2010-08-18  

freewxy 写道

看着还是有点吃力，这种经典的东西应该多编几次

刘容学长（xio chang） （我觉得应该是你，如果猜错了就不好意思了啊！）……确实，这种东西应该要多编几次。

尤其是Huffman编码的那儿

2 楼 freewxy 2010-08-17  

看着还是有点吃力，这种经典的东西应该多编几次

1 楼 沈冠军 2010-08-17  

,要是能把胡哥说的那个功能给搞出来的话就厉害了啊