菜鸟说：哈夫曼树及哈弗曼编码

终于把哈夫曼树及哈弗曼编码弄好了~

 

哈夫曼树就是最优二叉树

 

和上次的搜索二叉树一样，哈夫曼树也有它特定的构造规则：

 

1.要把要存入哈夫曼树的数据分别创建一个树

 

2.把这些树按照大小顺序排序（在Java里面用优先队列PriorityQueue非常方便）

 

3.去两个最小的树，把他们合并在一块儿，并把合并后的树放回队列，如此递归往复……

 

4.把最后剩下的那个树设置为根节点。

 

这样，哈夫曼树就构造完成了~

 

检查方法就是把哈夫曼树的所有叶结点的编码都输出来，向左走编码为0，向右走编码为1（根据自己规定）

 

然后再根据编码把树画出来，检查~

 

首先是节点类：

/**
 * 哈夫曼树节点类
 * @author Micro
 *
 */
public class HafNode implements Comparable<HafNode>{
	private HafNode father;
	private HafNode left;
	private HafNode right;
	private int num;
	
	//重载构造器
	public HafNode (int num) {
		this.num=num;
	}
	
	
	public HafNode getFather() {
		return father;
	}
	public void setFather(HafNode father) {
		this.father = father;
	}
	public HafNode getLeft() {
		return left;
	}
	public void setLeft(HafNode left) {
		this.left = left;
	}
	public HafNode getRight() {
		return right;
	}
	public void setRight(HafNode right) {
		this.right = right;
	}
	public int getNum() {
		return num;
	}
	public void setNum(int i) {
		this.num = i;
	}

	//设置要比较的对象
	@Override
	public int compareTo(HafNode o) {
		// 要比较的是数字大小
		int P = o.getNum();
		return num-P;
	}
}

 

 然后就是建树过程和输出哈弗曼编码：

 

import java.util.PriorityQueue;

/**
 * 创建哈夫曼树并获得各叶节点的哈弗曼编码
 * 
 * @author Micro
 * 
 */
public class HafTest {

	// 创建根节点
	private static HafNode root;

	// 程序入口
	public static void main(String[] args) {
		// 创建一个数组
		int[] a = { 1, 4, 3, 5, 6 ,4,6,7,6};
		// 创建优先队列
		PriorityQueue<HafNode> queue = new PriorityQueue<HafNode>();
		HafTest ht = new HafTest();
		// 把每个数新建一个节点
		for (int i = 0; i < a.length; i++) {
			HafNode hf = new HafNode(a[i]);
			queue.add(hf);
		}
		ht.HafTree(queue);
		String Code = "";
		ht.print(root, Code);
	}

	// 创建哈夫曼树
	public void HafTree(PriorityQueue<HafNode> queue) {
		while (queue.size() > 1) {
			HafNode min1, min2;
			min1 = queue.poll();
			min2 = queue.poll();
			// 创建合并的节点
			HafNode result = new HafNode(min1.getNum() + min2.getNum());
			result.setLeft(min1);
			result.setRight(min2);
			min1.setFather(result);
			min2.setFather(result);
			queue.add(result);
		}
		root = queue.peek();
	}

	// 打印叶节点
	public void print(HafNode a, String Code) {

		if (a.getLeft() == null && a.getRight() == null) {
			System.out.println(a.getNum() + "的哈夫曼编码为：" + Code);
		}
		if (a.getLeft() != null) {
			print(a.getLeft(), Code + '0');
		}
		if (a.getRight() != null) {
			print(a.getRight(), Code + '1');
		}
	}
}

 

输出的结果为：

 

4的哈夫曼编码为：000

1的哈夫曼编码为：0010

3的哈夫曼编码为：0011

4的哈夫曼编码为：010

5的哈夫曼编码为：011

6的哈夫曼编码为：100

6的哈夫曼编码为：101

6的哈夫曼编码为：110

7的哈夫曼编码为：111

恩~~没有错误~~

 

这样，一个最基本的哈夫曼树就完成了，下面就是利用这个树实现文件的压缩~加油~~~

评论

2 楼 jcs130 2011-08-11  

javafound 写道

那要搞清楚为何用PriorityQueue会方便啊?

恩~谢谢指教啦~~

1 楼 javafound 2011-08-11  

那要搞清楚为何用PriorityQueue会方便啊?