最优二叉树（哈弗曼树）

   提到哈弗曼树就必须提到节点权值，权值一般具有实际意义，比如此节点出现的概率，次数等。
必须提供权值才能构建出一棵哈弗曼树，因为哈弗曼树的定义为带权路径长度最小的二叉树。
树的带权路径长度为所有叶子节点的带权路径长度。
节点的带权路径长度为该节点到树的路径长度乘以节点权值。
哈希曼树最主要的应用是产生哈希曼编码。
为特点元素设计哈希曼编码要求二进制编码尽可能的短，并且任意一个字符的编码不是另外一个
字符的编码的前缀。


下面通过java代码构建哈希曼树与设计哈希曼编码

package com.algorithm;

/**
 * 最优二叉树（哈夫曼树）
 * 根据元素的权值构建哈夫曼树，并设计其哈弗曼编码
 * 使用数组存储节点
 */
public class Hufuman {
	private int[] weights;		//存储权值
	private int n;
	private TreeNode[] nodes;	//存储节点的数组
	private int m;		//数组长度
	
	
	class TreeNode{
		int weight;		//权值
		int Parent;		//父节点的下标
		int lchild;		//左孩子下标
		int rchild;		//右孩子下标
		
		public TreeNode(int weight,int parent,int lchild,int rchild){
			this.weight = weight;
			this.Parent = parent;
			this.lchild = lchild;
			this.rchild = rchild;
		}
	}
	
	public Hufuman(){
		
	}
	
	public Hufuman(int[] w){
		this.weights = w;
		int n = w.length;
		if(n <= 1){
			throw new IllegalArgumentException();
		}
		this.n = n;
		init();
	}
	
	/**
	 * 初始化节点数组
	 */
	private void init(){
	    m = 2*n - 1;
		nodes = new TreeNode[m];
		int i;
		for(i = 0;i < n ;++i){
			nodes[i] = new TreeNode(weights[i], -1, -1, -1);	//-1表示无父或孩子节点
		}
		for(;i < m;++i){
			nodes[i] = new TreeNode(-1, -1, -1, -1);
		}
	}
	
	/**
	 * 根据权值构建哈夫曼树
	 */
	public void create(){
		int min,secmin;
		for(int i = n;i < m;++i){
			int[] mins = select(i-1);
			min = mins[0];
			secmin = mins[1];
			nodes[min].Parent = i ;
			nodes[secmin].Parent = i;
			nodes[i].lchild = min;
			nodes[i].rchild = secmin;
			nodes[i].weight = nodes[min].weight + nodes[secmin].weight;

		}
	}
	
	/**
	 * 从叶子节点逆向求每个字符的哈弗曼编码
	 */
	public String[] hufumanCoding(){
		String[] codes = new String[n];
		StringBuilder sb ;
		for(int i=0;i<n;++i){	//i到n都是叶子节点
			sb = new StringBuilder();
			for(int c=i,p=nodes[i].Parent;p!=-1;c=p,p=nodes[p].Parent){
				if(nodes[p].lchild == c)
					sb.append('0');		//左分支表示字符'0'
				else	
					sb.append('1');		//右分支表示字符'1'
			}
			codes[i] = sb.reverse().toString();
		}
		return codes;
	}
	
	/**
	 * 取weight最小的两个节点
	 */
	private int[] select(int last){
		int min=0;		//最小值下标
		int secmin=0;		//次小值下标
		int i;
		for(i=0;i<=last;++i){
			if(nodes[i].Parent==-1){
				min = i;
				break;
			}
		}
		for(i=i+1;i<=last;++i){
			if(nodes[i].Parent==-1){
				secmin = i;
				break;
			}
		}
		int temp;
		if(nodes[min].weight > nodes[secmin].weight){
			temp = min;
			min = secmin;
			secmin = temp;
		}
		for(i=i+1;i<=last;++i){
			if(nodes[i].Parent!=-1)continue;
			if(nodes[i].weight < nodes[min].weight){
				secmin = min;
				min = i;
			}else{
				if(nodes[i].weight < nodes[secmin].weight)
					secmin = i;
			}
		}
		int[] minValues = {min,secmin};
		return minValues;
	}
	
	public void printTree(){
		System.out.println("   | weight | parent | lchild | rchild |");
		for(int i=0;i<m;i++){
			System.out.print(i+"  |   "+nodes[i].weight+"   |   "+nodes[i].Parent+"   |   "+nodes[i].lchild+"   |   "+nodes[i].rchild+"   |");
			System.out.println();
		}
	}
	
	public static void main(String[] args) {
		int[] w = {5,29,7,8,14,23,3,11};
		Hufuman t = new Hufuman(w);
		t.create();
		t.printTree();
		String[] str = t.hufumanCoding();
		for(String s:str){
			System.out.println(s);
		}
	}
		
}