哈夫曼树(最优二叉树)

....差点忘记写博客了...

 

 

哈夫曼树 .. 其实就是只利用叶子结点来存储要用信息的树,只不过它在构造的时候就拥有了一个迷人的特性... 就是WPL(带权路径长度)是最小的.. 而且还能用这个树的来为叶子结点中的信息进行编码, 得出来的各个编码一定不会相同,并且不会产生混淆的情况..

 

通过哈夫曼树的特点.实现了根据一个队列来创建一棵哈夫曼树的方法.

/**
	 * 得到随机产生的队列
	 */
	public void setQueue() {
		Random rd = new Random();
		System.out.println("随机产生的队列为:");
		for (int i = 0; i < 10; i++) {
			int k = rd.nextInt(20);
			TreeNode tn = new TreeNode(k);
			queue.add(tn);
			System.out.print(k + " ");
		}
		System.out.println();
	}

	// 得到队列
	public PriorityQueue<TreeNode> getQueue() {
		return queue;
	}

	// 建树,while (queue.size()>=2)
	public TreeNode CreatTree(PriorityQueue<TreeNode> queue) {
		TreeNode lc = queue.poll();
		TreeNode rc = queue.poll();
		// 两个最小的结点通过这个结点连接起来
		TreeNode tr = new TreeNode((Integer) lc.getData()
				+ (Integer) rc.getData());
		tr.setLchild(lc);
		tr.setRchild(rc);
		lc.setParent(tr);
		rc.setParent(tr);
		// 将其父结点放入队列.
		queue.add(tr);
		return tr;// 将根结点返回.当返回到最后一个根结点时就构成了一棵树
	}

 到此.. 哈夫曼树就建成了. 接下来就是哈夫曼编码了.这个的实现我用到了递归,并且是每个叶结点往回找

 

/**
	 * 为每个叶结点编码,返回字符串
	 * 
	 * @param leaf每次传入一个叶结点
	 * @return以字符串形式返回每个叶结点的哈夫曼编码
	 */
	public String ToCode(TreeNode leaf) {
		String s = "";
		// 叶结点存在双亲结点.
		if (leaf.getParent() != null) {
			if (leaf.getParent().getLchild() == leaf) {
				// 向父结点递归
				s = ToCode(leaf.getParent()) + 0;
				return s;// 叶结点为左孩子时,在递归得到的编码后面加个0;
			} else if (leaf.getParent().getRchild() == leaf) {
				// 向父结点递归
				s = ToCode(leaf.getParent()) + 1;
				return s;// 叶结点为右孩子时,在递归得到的编码后面加个1;
			}
		}
		return s;
	}

 

 通过这个方法.. 实现对哈夫曼树中叶子结点进行哈夫曼编码的

 

 

 

补充个.. 今天读取文件中的字节时..发现0出现的次数是最多的 ... 读了个162M的文件.. 0的个数比其他的数出现的次数多了10万次 ....