【JAVA算法】贪心算法 -- 哈夫曼编码解码

写在前面：

    我也是一名java语言的爱好者，仅以此文作为学习的记录，对于文中出现的代码规范，代码格式，算法效率等问题，希望各路大神不吝赐教，在下感激不尽。同是学习的同学也同样希望互相交流，取长补短。                                                                                                                                            

——[e-mail]

一.问题描述

    假设有一个文件，只包含字符a,e,i,s,t,space,newline，这七个字符出现次数分别是10，15，12，3，4，13，1。如果用等长编码表示需要log7向上取整为3比特表示。则整个文件有(10+15+12+3+4+13+1)*3 = 174bit。

                                                 

    在现实中，文件可能是很大的，许多相当大的文件是某个程序的输出程序，而在使用频率最大和最小的字符之间通常存在很大差别，如果对于所有不同频率的字符使用相同长度的编码，会导致文件空间的浪费，更科学的方式可以想到，对于出现频率低的字符使用较长的编码，而频率高的字符使用较短的编码。

    用二叉树来表示代表字符的二进制编码的分配过程。需要注意一点，这里的二叉树一定是一颗满树，即所有的节点要么是叶子节点，要不有两个子节点。

                            

                                                       

可以看到此时总大小为146

这里给出我的实现

import java.util.Collection;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Scanner;
//哈夫曼编码
public class Main {

	/**
	 * @param args
	 */
	private static LinkedList<HufNode> hufList = new LinkedList<HufNode>();//容器存放节点值
	class HufNode implements Comparable<HufNode>{
		int value;
		String name;
		HufNode Lchild = null;
		HufNode Rchild = null;
		public HufNode(){
			
		}
		public HufNode(int v,String s){
			value = v;
			name = s;
		}
		public HufNode(HufNode l,HufNode r){
			Lchild =l;
			Rchild =r;
			value = Lchild.value + Rchild.value;

		}
		@Override
		public int compareTo(HufNode node1) {
			// TODO Auto-generated method stub
			if (value<node1.value) {
				return -1;
			}else if (value == node1.value) {
				return 0;
			}else {
				return 1;
			}
		}
	}
	//哈夫曼编码
	public static void HufmanCode(){
		if (hufList.size()==1) {
			return;
		}
		while(hufList.size()>1){
			Collections.sort(hufList);
			HufNode node = new Main().new HufNode(hufList.get(0),hufList.get(1));
			hufList.remove();
			hufList.remove();
			hufList.add(node);
		}//此时hufList中只有一个元素，这就是编码后的哈夫曼树的根节点
	}
	//解码，后序遍历
	public static void decode(HufNode n,String code){
		if ((n.Lchild==null)&&(n.Rchild==null)) {
			System.out.print("元素值为 "+n.name+"   编码为："+code);
			System.out.println();
			return;
		}
		decode(n.Lchild, code+"0");
		decode(n.Rchild, code+"1");
		return;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();//待编码元素个数
		for(int i=0;i<N;i++){
			hufList.add(new Main().new HufNode(scanner.nextInt(),scanner.next()));
		}
		HufmanCode();
		decode(hufList.get(0), "");
	}

}