学习哈夫曼树--------两部曲

    学习一样事物，自然要先明其义，再通其用。哈夫曼树，顾名思义是一种树，不过它是一类带权路径最短的树。何谓权值呢？权值就是定义的路径上面的值。可以这样理解为结点间的距离；它通常指字符对应的二进制编码出现的概率。至于哈夫曼树中的权值可以理解为：权值大表明出现概率大！一个结点的权值实际上就是这个结点子树在整个树中所占的比例.

 

举一个网上给的例子：

abcd四个叶子节点的权值为7,5,2,4. 这个7,5,2,4是根据实际情况得到的,比如说从一段文本中统计出abcd四个字母出现的次数分别为7,5,2,4. 说a结点的权值为7,意思是说a结点在系统中占有7这个份量.实际上也可以化为百分比来表示,但反而麻烦,实际上是一样的.

由此哈夫曼树叶称作最优树或二叉树，不过这里要注意完全二叉树不一定就是最优二叉树呦！！那么哈夫曼树怎样构造呢？它的构造方式如下：

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：

(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；

(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

(3)从森林中删除选取的两棵树，并将新树加入森林；

(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

 

嗯，现在哈夫曼树的定义以及构造方式已经描述完了，就差通过代码把这个过程实现。通过两部曲，我们把哈夫曼树构造理解清楚！

在此之前，你会不会有疑问：为什么这样构造就能确保带权路径最小呢？？？我们在高中接触过排序不等式公式，如下：

0<a1<a2<a3......<an      0<b1<b2<b3......<bn

然后有：an×bn+an-1×bn-1+......+a1×b1>=乱序和>=a1×bn+a2×bn-1+......+an×b1

构建哈夫曼树的方法使权值越大的节点离根节点越近，而权值越小的节点离根节点越远，如此便能保证带权路径最小了！

 

第一曲：手工构造！！

手工构造，其实非常简单，就是自己创建几个节点，然后建立节点之间的关系，形成一棵树，左节点上的权值为0，右节点未1，父节点也为1，最后把叶子节点的编码打印出来。这个过程实际上就是帮助我们更好地理解哈夫曼树的构造过程，为自动建树巩固基础！

第二曲：自动建树！！

通过给定一个字符串，然后统计相同字符出现的次数，再根据这些次数自动创建哈夫曼树，再输出叶子节点的编码。

代码如下：

public class HFMTreeCode {

	class Node{
		
		private Node left;//左节点
		private Node right;//右节点
		private Node parent=null;//父节点
		private int  data;//数据
		
	}
	
	private Node root;//根节点
	
	//哈夫曼树的手工建造
	public Node TreeCreat(){
		//                       19
		//               8                   11
		//            4     4             5      6
		//         2     2
				
		
		Node n1=new Node();
		n1.data=2;
		
		Node n2=new Node();
		n2.data=2;
		
		Node n3=new Node();
		n3.data=n1.data+n2.data;
		n3.left=n1;
		n3.right=n2;
		
		Node n4=new Node();
		n4.data=4;
		
		Node n5=new Node();
		n5.data=5;
		
		Node n6 =new Node();
		n6.data=6;
		
		Node n7=new Node();
		n7.data=n3.data+n4.data;
		n7.left=n3;
		n7.right=n4;
		
		Node n8=new Node();
		n8.data=n5.data+n6.data;
		n8.left=n5;
		n8.right=n6;
		
		Node n9=new Node();
		n9.data=n7.data+n8.data;
		n9.left=n7;
		n9.right=n8;
		
		root=n9;
		
		return root;
		
	}
	

	
	//输出哈夫曼树的编码
	public void Treeprint(int []data)
	{   
		Node []nodes=new Node[data.length];//创建一个节点类型的数组
		
		//遍历数组，将data数组里的数据传给nodes数组里data数据
		for(int i=0;i<nodes.length;i++)
		{
			nodes[i]= new Node();
			nodes[i].data=data[i];
		}
				
		while(nodes.length>1)
		{
			//排序
			BubbleSort(nodes);
			//找到最小的两个值，然后生成新结点
			Node node1=new Node();
			Node node2=new Node();
			node1=nodes[0];
			node2=nodes[1];
			
			Node newNode=new Node();
			newNode.left=node1;
			newNode.right=node2;
			newNode.data=node1.data+node2.data;//新结点数据之值为nodes数组两个含最小data数值的节点它们data值之和
			
			//创建一个新Node类型数组，存放原来nodes数组中除两个含最小data值的node外其他node和新结点
			Node[]node1s=new Node[nodes.length-1];
			for(int i=2;i<nodes.length;i++)
			{
				node1s[i-2]=nodes[i];
			}
			
			node1s[node1s.length-1]=newNode;
			
			nodes=node1s;//交换两个数组地址
						
		}
		
		
		root=nodes[0];
		
		TreePrint(root,"");
		
	}
	//打印当前节点的编码，用递归的思想
	public void TreePrint(Node node ,String code){
		
		if(node!=null){
			if(node.left==null&&node.right==null)
			{//只打印出需要的节点编码
		      System.out.println(node.data+"编码是"+code);
			}
		      TreePrint(node.left,code+"0");//递归调用打印左节点编码，每次都+0
		      TreePrint(node.right,code+"1");//递归调用打印右节点编码，每次都+1
		    
		}
	}
	
	/*
	 * 冒泡法
	 */
	public void BubbleSort(Node [] array)
	{    
		 
		//循环遍历数组
		for(int i=0;i<array.length;i++)
		{
			for(int j=i+1;j<array.length;j++)
			{
				if(array[i].data>array[j].data)
				{
					Node temp = new Node();
					temp=array[i];
					array[i]=array[j];
					array[j]=temp;
				}
			}
		}
		
	}
	/*
	 * 交换数组元素的方法
	 */
	public void swap(Node [] array,int x,int y)
	{
		Node temp=null;//设置一个中间变量，先初始化为0
		//交换过程
		temp=array[x];
		array[x]=array[y];
		array[y]=temp;
		
	}
	/**
	 * @param args
	 */
	/*
	 * 统计一个字符串中不同字符的次数，并返回一个存入次数的整型数组
	 */
	
	public int[]arrayPrint(String str)
	{  
		String str1="";//创建一个存储不含重复字符的字符串
		
		for(int i=0;i<str.length();i++)
		{
			char c=str.charAt(i);
			if(str1.indexOf(c)==-1)
			{//如果str1中不含c
				str1+=c;//则将c加到str1上
			}
		}
		
		
		int []array=new int[str1.length()];
		//遍历数组，把字符出现的次数加到整型数组array[]中
		for(int i=0;i<str1.length();i++)
		{
			char ch1=str1.charAt(i);
			array[i]=getCount(str,ch1);
		}
		for(int i=0;i<array.length;i++)
		{
			System.out.println(array[i]);
		}
			return array;
	}
	/*
	 * 统计一个字符在字符串中出现的次数
	 */
	public int getCount(String str,char ch)
	{  
		int count=0;
		for(int i=0;i<str.length();i++)
	 {  
		if(str.charAt(i)==ch)
	            count++;
	   
     }
		return count;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//int[]array={1,4,5,8,2};	
		String str="dfsdfdsfsdfsdfsdasdas";
		
		
        HFMTreeCode htc=new HFMTreeCode();
      
        htc.Treeprint(htc.arrayPrint(str));
	}

}

 说明下，这里不需要另外创建一个结点类，而是直接在这个类内部中创建，因为结点类一般不会被其他类所使用，它的创建单纯是为了这个类的实现。

接下来，在完成了这些后，我们就可以开始朝哈夫曼压缩方面努力了！！！

评论

1 楼 梳子不爱头发 2015-03-28