哈夫曼树

哈夫曼树：又称最优树（二叉树），是一类带权路径最短的树。

 

结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。

树的带权路径长度：树中所有叶子结点的带权路径长度之和，记做WPL

WPL为最小的二叉树就称作最优二叉树或哈夫曼树。

 

哈夫曼树的构造：

（1）将结点按照权值从小到大排列。

（2）每次取前两个权值最小的结点作为左右子树，其根节点的权值为这两个子树结点权值之和。

（3）将原两个结点权值最小的结点从排列中删除，并将这两个结点的根结点加入排列中。

（4）重复（1）（2）（3），直到最后只剩下一个结点为止。则哈夫曼树构造成功。

例如：

 

在代码中，使用优先队列构建哈夫曼树。
 

哈夫曼编码：从哈夫曼树根结点开始，左0右1，即对左子树分配代码"0"，右子树分配代码"1",一直到叶子结点为止，然后将从树根沿每条路径到达叶子结点的代码排列起来，便得到了哈夫曼编码。

如上例：由哈夫曼树获得每个字母编码为：

a : 0 ;  b : 10 ;  c : 110 ;  d : 111 ;

 

哈夫曼压缩：无损的压缩算法，一般用来压缩文本和程序文件。个体符号用一个特定长度的位序列替代，在文件中出现频率高的，使用短的位序列，而那些很少出现的符号，则用较长的位序列。如将字符转化为它们的01串。
 

public class hfmTree {
	private hfmNode root;
	private int size;
	private int i=0;
	
	Comparator<hfmNode> OrderIsdn=new Comparator<hfmNode>(){

		@Override
		public int compare(hfmNode node1, hfmNode node2) {
			// TODO Auto-generated method stub
			int numbera=node1.getTimes();
			int numberb=node2.getTimes();
			if(numberb>numbera){
				return -1;
			}else if(numberb<numbera){
				return 1;
			}else{
				return 0;
			}
		}
		
	};
	public void createTree(int [] CountArray){
		//优先队列
		PriorityQueue<hfmNode> nodeQueue=new PriorityQueue<hfmNode>(10,OrderIsdn);
		//把所有的结点都加入到队列里面去
		for(int i=0;i<CountArray.length;i++){
			if(CountArray[i]!=0){
				hfmNode node=new hfmNode(i+97,CountArray[i]);
				nodeQueue.add(node);//加入结点
			}
		}
		size=nodeQueue.size();
		//构建哈夫曼树
		while(nodeQueue.size()>1){
			hfmNode min1=nodeQueue.poll();//获取队列头
			System.out.print(min1.getTimes()+"   ");
			System.out.println();
			hfmNode min2=nodeQueue.poll();
			hfmNode result=new hfmNode(0,min1.getTimes()+min2.getTimes());
			result.setlChild(min1);//将最小的设为左子树
			result.setrChild(min2);//将第二小的设为右子树
			nodeQueue.add(result);//加入合并结点
		}
		root=nodeQueue.peek();//得到根结点
	}
	public void getMB(hfmNode root,String s){
		Code [] SaveCode=new Code [size];
		if((root.getlChild()==null)&&root.getrChild()==null){
			Code hc=new Code();
			hc.setNode(s);
			hc.setN(s.length());
			System.out.println("结点  "+(char)(root.getData())+" 编码  "+hc.getNode());
			SaveCode[i++]=hc;//保存字节
		}
		if(root.getlChild()!=null){//左0右1
			getMB(root.getlChild(),s+'0');
		}
		if(root.getrChild()!=null){
			getMB(root.getrChild(),s+'1');
		}
	}

  注意：应该让优先队列按照你给的自然顺序对结点进行排列，此处是需要对结点的权值进行排列，所以需要重写Comparator类中的compare()方法，否则会出现类转换异常。