数据结构之哈夫曼树（java实现）

所谓哈夫曼树就是要求最小加权路径长度，这是什么意思呢？简而言之，就是要所有的节点对应的路径长度（高度-1）乘以该节点的权值，然后保证这些结果之和最小。

哈夫曼树最常用的应用就是解决编码问题。一般我们用的ASCII是固定长度的编码，对于那些常用的字符，使用很长的长度就显得略为浪费空间了。

下面以一个实例来构建一颗哈夫曼编码树。

设字符集S={A，B，C，D，E，F}，字符出现的频率W={2，3，5，7，9，12}，对字符集进行哈夫曼编码

（1）以频率为树的节点值，构建6个树节点，保存在一个数据集合T中

(2)选择频率集W中最小的两个频率，然后相加，将结果作为树的节点值，构建新的树节点，将这两个最小值对应的树节点，分别作为新的节点的左右孩子。从T重删除这两个最小值对应的节点，最后将新节点放到T中。

（3）重复第2步，直到T中只剩下一个节点，那么该节点就是所需要的哈夫曼树

其实说的容易，实现起来也有一点小麻烦，下面用java实现：

树节点：

 

public class TreeNode
	{
        public TreeNode leftNode;
        public TreeNode rightNode;
        public T data;
		public TreeNode(T data)
			{
				this.data=data;
			}
	}

构建哈夫曼树：

 

 

public class TestTree
	{
		/*
		 * 设S={A,B,C,D,E,F},W={2,3,5,7,9,12}
		 */
		static HashMap map;
		public TestTree()
			{
				// TODO Auto-generated constructor stub
			}

		public static void main(String[] args)
			{
				Character[] character = { 'A', 'B', 'C', 'D', 'E', 'F' };
				int[] weight = { 2, 3, 5, 7, 9, 12 };// 有序或者无序都一样
				map=new HashMap();
				for(int i=0;i> nodes = new ArrayList<>>();
				for (int i = 0; i < weight.length; i++)
					{
						nodes.add(new TreeNode(weight[i]));
					}
				while (true)
					{
						if (nodes.size() <= 1)
							break;
						// 找两个最小的
						TreeNode minNode = nodes.get(0);
						TreeNode sminNode = nodes.get(1);
						for (int i = 1; i < nodes.size(); i++)
							{
								TreeNode tempNode = nodes.get(i);
								if (minNode.data >=tempNode.data)
									{
										sminNode = minNode;
										minNode = tempNode;
									}
							}
						nodes.remove(minNode);
						nodes.remove(sminNode);
						TreeNode newNode = new TreeNode(
								minNode.data + sminNode.data);
						newNode.leftNode = minNode;
						newNode.rightNode = sminNode;
						nodes.add(newNode);
					}
				TreeNodehafmanTreeNode=nodes.get(0);
				getHalmanCode(hafmanTreeNode," ");
				
			}
		 public static void getHalmanCode(TreeNodehafmanTreeNode,String blank)
		 {
			 if(hafmanTreeNode==null)
				 return;
			 if(hafmanTreeNode.leftNode==null&&hafmanTreeNode.rightNode==null)
				 {
				   System.out.println("->"+getCharacter(hafmanTreeNode.data));
				 }
			 else 
				 {
					 System.out.print("0");
					 getHalmanCode(hafmanTreeNode.leftNode,blank+" ");
					 System.out.print(blank+"1");
					 getHalmanCode(hafmanTreeNode.rightNode,blank+" ");
				 }
		 }
		 //得到某一个字符的编码
		 public static void getHalmanCode(TreeNodehafmanTreeNode,Character character)
		 {
			 if(hafmanTreeNode==null)
				 return;
			 if(hafmanTreeNode.leftNode==null&&hafmanTreeNode.rightNode==null)
				 {
					 if (getCharacter(hafmanTreeNode.data)==character)
						{
							System.out.print("");
						}
				 }
		 }
                //得到权值对应的字符
		 public static Character getCharacter(int weight)
		 {
			 Set<>>set=map.entrySet();
			 for(Iterator<>> iterator=set.iterator();iterator.hasNext();)
				 {
					 Map.Entryentry=iterator.next();
					 if(entry.getValue()==weight)
						 {
							 map.remove(entry.getKey());
							 return entry.getKey();
						 }
				 }
			 return null;
		 }
	}

结果:

 

D:00

E:01

A:1000

B:1001

C:101

F:11