huffmantree.java

来自「《算法设计与分析》王晓东编著」· Java 代码 · 共 59 行

public class HuffmanTree {
	public static Bintree huffmanTree(float[] f)
	{
		// 生成单结点树
		int n=f.length;
		Huffman[] w=new Huffman[n+1];
		
		for (int i=0;i<n;i++)
		{
			Bintree x=new Bintree();
			x.makeTree(i,null,null);
			w[i+1]=new Huffman(x,f[i]);
		}
		
		// 建立最小堆
		MinHeap H=new MinHeap();
		H.initialize(w,n);
		
		// 反复合并最小频率树
		for (int i=1;i<n;i++)
		{
			Huffman x=(Huffman)H.removeMin();
			Huffman y=(Huffman)H.removeMin();
			Bintree z=new Bintree();
			z.makeTree(-1,x.tree,y.tree);
			Huffman t=new Huffman(z,x.weight+y.weight);
			H.put(t);
		}
		
		return ((Huffman)H.removeMin()).tree;
	}
	
	/* 遍历二叉树，输出每个字符的Huffman编码 */
	public static void Output(Bintree tree,char[] c,String code)
	{
		if (tree.left==null && tree.right==null)
		{
			System.out.println(c[tree.nodeIndex]+" : "+code);
			return;
		}
		
		if (tree.left!=null)
			Output(tree.left,c,code+"0");
		if (tree.right!=null)
			Output(tree.right,c,code+"1");	
	}
	
	public static void main(String args[])
	{
		float[] f=new float[]{45,13,12,16,9,5};
		char[] chars=new char[]{'a','b','c','d','e','f'};
		
		Bintree tree=huffmanTree(f);
		Output(tree,chars,"");
	}

}