哈夫曼树和编码

 

 

哈夫曼树:所有的叶子节点的加权路径和最小的

 

 

哈夫曼编码：每个叶子节点的编码

 从跟节点到达该叶子节点经历的路径（枝节点）

 左枝节点：0   右枝节点：1

每个叶子节点的路径都可以转成一个01字符串，这个01串就是哈夫曼编码

 

 

 

根据给定的数组创建哈夫曼树和哈夫曼编码:代码如下

 

package com.HuffmanCode;
/**
 * @author Administrator
 * 创建哈夫曼编码的节点类
 */
public class TreeCode {
	
	//属性
	int obj;
	TreeCode LeftChild;
	TreeCode RightChild;
	public TreeCode parent;
	int flag = -1;//根节点为-1,左1,右0
	
	//创建对象时需要的参数
	public TreeCode(int obj){
		this.obj = obj;
	}
	
	//重写toStringde 方法
	public String toString(){
		return String.valueOf(obj);
	}
	

}

 

 

 

package com.HuffmanCode;

import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Set;
/**
 * 创建哈夫曼树,并得到哈夫曼编码
 * 
 * @author Administrator
 * 
 */
public class Huffman {

	public static void main(String[] args) {
		
		Huffman tree = new Huffman();
		// 根据给定的数组创建哈夫曼树
		int array[] = { 1, 3, 2, 4, 5 };

		// 创建队列节点
		PriorityQueue<TreeCode> queueList = tree.creatNode(array);
		// // 遍历队列
		// while (queueList.size() > 0) {
		// System.out.println(queueList.poll());
		// }

		// 根据队列节点创建树
		TreeCode root = tree.creatTreeNode(queueList);
		// 打印输出树
		tree.printTree(root);

		// 创建并输出节点的编码
		HashMap<TreeCode, String> map = tree.creatCode(root);
              //遍历HashMap队列中的哈夫曼编码
		Set<TreeCode> code = map.keySet();
		for (TreeCode s : code) {
			String v = map.get(s);
			System.out.println(s + "<<<>>>>>" + v);
		}

	}

	// 打印树的方法;
	public void printTree(TreeCode root) {
		// 判断节点是否寻在
		if (root != null) {
			// 输出根节点
			System.out.println(root);
			// 输出左节点
			TreeCode left = root.LeftChild;
			printTree(left);
			// 输出右节点
			TreeCode right = root.RightChild;
			printTree(right);

		}
	}

	/**
	 * 创建节点并排序
	 * 
	 * @param array根据数组创建节点
	 * @return 返回队列
	 */
	public PriorityQueue<TreeCode> creatNode(int array[]) {

		PriorityQueue<TreeCode> queueList = new PriorityQueue<TreeCode>(11,
				new Comparator<TreeCode>() {
					// 创建匿名类来重写排序方法
					@Override
					public int compare(TreeCode o1, TreeCode o2) {
						// 返回排序规则
						return o1.obj - o2.obj;
					}

				});

		// 遍历并创建节点
		for (int i = 0; i < array.length; i++) {
			TreeCode code = new TreeCode(array[i]);
			queueList.add(code);
		}

		return queueList;

	}

	/**
	 * 根据节点创建树
	 * 
	 * @param queueList传入的队列
	 * @return 返回树根
	 */
	public TreeCode creatTreeNode(PriorityQueue<TreeCode> queueList) {
		while (queueList.size() > 1) {
			// 去除前两个元素
			TreeCode n1 = queueList.poll();
			TreeCode n2 = queueList.poll();
			// 根据去除最前面的两个数创建新的节点

			TreeCode n3 = new TreeCode(n1.obj + n2.obj);
			// 设置n1,n2,n3之间的关系及位置
			n3.LeftChild = n1;
			n3.RightChild = n2;
			n1.flag = 1;
			n2.flag = 0;

			n1.parent = n3;
			n2.parent = n3;

			// 将根节点放入队列
			queueList.add(n3);
		}

		// 取出根节点
		TreeCode root = queueList.poll();

		// 将根节点放回
		return root;

	}

	/*
	 * 创建HsahMap队列来保存哈夫曼编码
	 */
	public HashMap<TreeCode, String> creatCode(TreeCode root) {

		HashMap<TreeCode, String> map = new HashMap<TreeCode, String>();
		// 调用创建哈夫曼编码的方法
		getTreeCode(root, null, map, "");

		return map;

	}

	/**
	 * 创建哈夫曼编码
	 */
	public void getTreeCode(TreeCode root, TreeCode parent,
			HashMap<TreeCode, String> map, String s) {
		// 节点是否存在
		if (root != null) {
			if (root.flag != -1) {
				s += root.flag;
			}
			// 遍历左边的编码
			TreeCode left = root.LeftChild;
			getTreeCode(left, root, map, s);

			// 遍历右边的编码
			TreeCode right = root.RightChild;
			getTreeCode(right, root, map, s);

		} else {
			map.put(parent, s);
		}

	}

}

 

输出结果:

哈夫曼树:

15

6

3

3

1

2

9

4

5

 

哈夫曼编码:

5<<<>>>>>00

2<<<>>>>>100

1<<<>>>>>101

4<<<>>>>>01

3<<<>>>>>11

上面的哈夫曼图 中的叶子节点 1,2应该在右边的3节点 下面