再次学习哈弗曼

       还记得第一次接触哈夫曼树是在大二的数据结构课上，大家也都知道哈树的生成规则，很简单也很容易理解。给你N个带权的节点，让你生成一颗哈树，相信大部分人都没有问题。而正是这种表面看似很简单的东西，我们就容易无视。我坦白，那年数据结构的学习，对于哈树这一块，我没有敲过一行代码，更没有去想过他存在的意义以及利用哈树能解决什么样的问题。

       大三进入蓝杰，重新接触到了哈夫曼树。这个沉寂在我脑海已久且濒临消亡的知识点，仿佛又渐渐地回来了。也让我开始思考哈夫曼树存在的意义。在IT这么一个日新月异的领域，一个技术之所以能够存在，一定是有其价值的，他一定是能给我们决绝问题带来利益的。通过查找给方面的资料，发现哈弗曼的用处确实很广，尤其是在数据通信、图像处理、数据压缩等方面有着很大的用处。

       下面，我想通过手动建造一棵哈夫曼树，再次走进哈夫曼的世界。 ------

一、哈弗曼的基础知识

      大家要了解一下哈夫曼树的基础知识。网上有很多解释，度娘说的比我清楚，这里就不占用篇幅多做解释。

     下图是建造一颗哈树的过程....

二、 进入主题--------代码的实现

     

    （1）首先，定义一个树的节点类

/**
 * 哈夫曼树节点的定义
 * 
 * @author Administrator
 * 
 */
public class HuffmanNode {
	// 成员属性
	private HuffmanNode left_child = null;
	private HuffmanNode right_child = null;
	private HuffmanNode parend = null;
	// 权值
	private int obj;

	public HuffmanNode getLeft_child() {
		return left_child;
	}

	public void setLeft_child(HuffmanNode left_child) {
		this.left_child = left_child;
	}

	public HuffmanNode getRight_child() {
		return right_child;
	}

	public void setRight_child(HuffmanNode right_child) {
		this.right_child = right_child;
	}

	public HuffmanNode getParend() {
		return parend;
	}

	public void setParend(HuffmanNode parend) {
		this.parend = parend;
	}

	public int getObj() {
		return obj;
	}

	public void setObj(int obj) {
		this.obj = obj;
	}

	// 构造函数
	public HuffmanNode(int obj) {
		this.obj = obj;
	}

}

 

（2）生成一颗哈树

         这里用到了一个新的知识点---优先队列。因为哈夫曼树的构造规则是每次要取根节点权值最小的两棵树出来。所以我们必须根据这些根节点权值大小，将这些树进行排序。 优先队列恰好为我们提供了这项功能，我们通过重新定义Comparator比较器，可以设定自己想要的排序规则，十分方便。

Comparator<HuffmanNode> comparator = new Comparator<HuffmanNode>() {

			@Override
			public int compare(HuffmanNode o1, HuffmanNode o2) {
				int numbera = o1.getObj();
				int numberb = o2.getObj();
				if (numberb < numbera) {
					return 1;
				} else if (numberb > numbera) {
					return -1;
				} else {
					return 0;
				}

			}
		};

 

核心语句----哈树的生成

              从森林中每次取根节点权值最小的两棵树出来，形成一棵新树，其权值为两树根绝点权值之和。并将这两棵树分别作为新树的左右子树。循环往复，知道深林中只剩下1棵树。那么，这棵树就是我们要找的哈夫曼树。

/**
	 *  生成哈夫曼树的方法
	 * @param queue 优先队列
	 */
	private void creathuffman(PriorityQueue<HuffmanNode> queue) {
		while (queue.size() != 1) {
			// 取得两个最小的节点
			HuffmanNode node1 = queue.poll();
			HuffmanNode node2 = queue.poll();
			// 生成一个新的节点
			HuffmanNode node3 = new HuffmanNode(node1.getObj() + node2.getObj());
			node3.setLeft_child(node1);
			node3.setRight_child(node2);
			queue.add(node3);
		}
	}

 

（3）打印所生成的哈树（通过先序遍历）

        

// 打印哈夫曼树的方法
	private void printhuffman(HuffmanNode rootnode) {
		// 指定根节点，从根节点开始找
		HuffmanNode temp = rootnode;
		// 打印根节点的值
		System.out.print("【"+temp.getObj()+"】" + "  ");
		if (rootnode.getLeft_child() != null) {
			temp = rootnode.getLeft_child();
			// 递归调用自己，表示只要左节点不为空，就把左节点作为新的根节点继续上边步奏
			printhuffman(temp);
		}
		if (rootnode.getRight_child() != null) {
			temp = rootnode.getRight_child();
			printhuffman(temp);// 同上
		}
	}

 

         至此，我们的哈夫曼树的生成过程已经演示完毕。刚才也说了，哈夫曼树的用处还有很多，我们能够创建他，也只是完成其中最基础的要求，我们不能止步于此。当然，我们不能认为这些东西很简单，就去轻视他，自己没有动手做过，你是不会知道什么叫做说着简单做着难的。

          好啦， 之后我们会通过一个文件压缩程序的演示，其中包括了哈弗曼编码的生成，对象的序列化，文件的读出与写入等问题，跟大家进一步分享哈弗曼在数据编码上的用途。