哈夫曼树和哈夫曼编码的Java实现

package com.eapple; public class HUFFManMain { /** * Author:李志远 * Date:2017-11-06 */ public static void main(String[] args) { // TODO Auto-generated method stub System.out.println("开始构建HuffMan树"); int[] i_quanzi={9,12,6,3,5,15}; //构建HuffMan节点个数,注意此处仅仅是定义了对象的引用，并没有内容 HuffManNode[] huffManNode=new HuffManNode[2*i_quanzi.length]; huffManNode[0]=new HuffManNode(); //初始化7点的权值，从1开始，舍弃0 for(int i=1;i<=i_quanzi.length;i++) { //对象初始化 huffManNode[i]=new HuffManNode(); huffManNode[i].setWeight(i_quanzi[i-1]); huffManNode[i].setLchild(0); huffManNode[i].setParent(0); huffManNode[i].setLchild(0); } //剩余用到的节点初始化 for(int i=i_quanzi.length+1;i<2*i_quanzi.length;i++) { //对象初始化 huffManNode[i]=new HuffManNode(); huffManNode[i].setWeight(0); huffManNode[i].setLchild(0); huffManNode[i].setParent(0); huffManNode[i].setLchild(0); } //开始构建HuffMan树 for(int i=i_quanzi.length+1;i<2*i_quanzi.length;i++) { int f_small1=100000; int i_small1=0; int f_small2=100000; int i_small2=0; //求出最小权值 for(int j=1;j<i;j++) { if(huffManNode[j].getParent()==0) { if(huffManNode[j].getWeight()<f_small1) { i_small1=j; f_small1=huffManNode[j].getWeight(); } } } //求出第二小权值 for(int j=1;j<i;j++) { if(huffManNode[j].getParent()==0) { if(huffManNode[j].getWeight()<f_small2&&huffManNode[j].getWeight()>f_small1) { i_small2=j; f_small2=huffManNode[j].getWeight(); } } } huffManNode[i].setLchild(i_small1); huffManNode[i].setRchild(i_small2); huffManNode[i].setWeight(f_small1+f_small2); huffManNode[i_small1].setParent(i); huffManNode[i_small2].setParent(i); } System.out.println("HT的状态如下所示："); for(int i=1;i<2*i_quanzi.length;i++) { System.out.println(i+" "+huffManNode[i].weight+" "+huffManNode[i].parent+" "+huffManNode[i].lchild+" "+huffManNode[i].rchild); } System.out.println("HuffMan编码为:"); //定义字符串用来存储编码结果 String[] s_HuffMan=new String[i_quanzi.length+1]; //定义节点的父亲和节点的当前数组序号 int i_parent,i_temp; for(int i=1;i<=i_quanzi.length;i++) { s_HuffMan[i]=new String(); //System.out.println(huffManNode[i].getWeight()+"的HuffMan编码为："); i_parent=0;i_temp=0; i_parent=huffManNode[i].getParent(); i_temp=i; while(i_parent!=0) { if(huffManNode[i_parent].getLchild()==i_temp) { s_HuffMan[i]=s_HuffMan[i]+"0"; } if(huffManNode[i_parent].getRchild()==i_temp) { s_HuffMan[i]=s_HuffMan[i]+"1"; } //保存当前序号 i_temp=i_parent; //得到当前节点的父亲节点序号 i_parent=huffManNode[i_parent].getParent(); } } for(int i=1;i<=i_quanzi.length;i++) { System.out.println(huffManNode[i].getWeight()+"的HuffMan编码为："); System.out.println(reverseString(s_HuffMan[i])); } } //字符串逆序输出函数 public static String reverseString(String string){ String resultString = ""; char[] charArray = string.toCharArray();//获得字符数组 for(int i = charArray.length-1;i>=0;i--){ resultString += charArray[i]; } return resultString; } }