哈夫曼樹及哈夫曼編碼Java實作

/**
 * 哈夫曼樹結點類
 * @author liangxiamoyi
 *
 */
public class HuffmanNode {
	/**
	 * 左子節點
	 */
	protected HuffmanNode left;
	/**
	 * 右子節點
	 */
	protected HuffmanNode right;
	/**
	 * 父親結點
	 */
	protected HuffmanNode father;
	/**
	 * 資料
	 */
	protected String item;
	/**
	 * 權值
	 */
	protected int weight;
	/**
	 * 構造方法
	 * @param item 字元
	 * @param left 左子節點
	 * @param right 右子節點
	 */
	public HuffmanNode(String item,HuffmanNode left,HuffmanNode right){
		this.item=item;
		this.left=left;
		this.right=right;
		this.weight=0;
		this.father=null;
	}
}
           

<pre name="code" class="java">import java.util.Scanner;

/**
 * 哈夫曼樹類
 * @author liangxiamoyi
 *
 */
public class HuffmanTree {
	/**
	 * 根節點
	 */
	private HuffmanNode root;
	/**
	 * data數組
	 */
	private String[] data;
	/**
	 * weight數組
	 */
	private int[] weight;
	/**
	 * 結點數
	 */
	private int nodeNum;
	/**
	 * 構造方法
	 * @param t 根節點
	 * @param nodeNum 節點數
	 */
	public HuffmanTree(HuffmanNode t,int nodeNum){
		this.root=t;
		this.nodeNum=nodeNum;
		this.data=new String[nodeNum];
		this.weight=new int[nodeNum];
	}
	/**
	 * 建立哈夫曼樹
	 */
	public void createHuffmanTree(){
		inputNodes();
		HuffmanNode[] h=new HuffmanNode[nodeNum];
		HuffmanNode p1,p2,p,t;
		for(int i=0;i<nodeNum;i++){
			h[i]=new HuffmanNode(null, null, null);
			h[i].item=new String(data[i]);
			h[i].weight=weight[i];
			h[i].left=h[i].right=h[i].father=null;
		}
		for(int i=0;i<nodeNum-1;i++){
			t=new HuffmanNode("#", null, null);
			p1=h[i];
			p2=h[i+1];
			t.weight=p1.weight+p2.weight;
			t.left=p1;
			t.right=p2;
			p1.father=p2.father=t;
			p=t;
			int j=i+2;
			while(j<nodeNum&&p.weight>h[j].weight){
				h[j-1]=h[j];
				j=j+1;
			}
			h[j-1]=p;
		}
		root=h[nodeNum-1];
	}
	/**
	 * 輸入結點資訊
	 */
	public void inputNodes(){
		Scanner sc=new Scanner(System.in);
		System.out.println("請輸入data數組：");
		for(int i=0;i<nodeNum;i++){
			data[i]=sc.next();
		}
		System.out.println("請輸入weight數組：");
		for(int i=0;i<nodeNum;i++){
			weight[i]=sc.nextInt();
		}
		//從小到大進行排序
		for(int i=0;i<weight.length-1;i++){
			for(int j=i+1;j<weight.length;j++){
				int temp;
				String str=new String();
				if(weight[i]>weight[j]){
					temp=weight[i];
					weight[i]=weight[j];
					weight[j]=temp;
					str=data[i];
					data[i]=data[j];
					data[j]=str;
				}
			}
		}
	}
	/**
	 * 搜尋葉節點
	 * @param root 根節點
	 * @param item 資料值
	 * @return 傳回葉節點
	 */
	public HuffmanNode find(HuffmanNode t,String item){
		HuffmanNode p;
		if(t==null)return null;
		else if(t.item.equals(item))return t;//内容相同
		else if((p=find(t.left,item))!=null)return p;
		else return find(t.right,item);
	}
	/**
	 * 獲得哈夫曼編碼
	 * @param item 資料值
	 */
	public void getHuffmanNode(String item){
		HuffmanNode p=find(this.root,item);
		if(p!=null){
			System.out.println("chenggong");
		}
		StringBuffer code=new StringBuffer();
		while(p!=null&&p.father!=null){
			if(p.father.left==p){
				code.append('0');
			}
			else{ 
				code.append('1');
			}
			p=p.father;
		}
		System.out.println(code.reverse());
	}
	/**
	 * 先根周遊
	 * @param t 根節點
	 */
	public void preOrder(HuffmanNode t){
		if(t!=null){
			System.out.print(t.item+" ");
			preOrder(t.left);
			preOrder(t.right);
		}
	}
	//測試
	public static void main(String[] args){
		HuffmanTree huffman=new HuffmanTree(null, 7);
		huffman.createHuffmanTree();
		huffman.preOrder(huffman.root);
		huffman.getHuffmanNode("s");
	}
}
           

測試結果：