内容比较详细： http://www.cnblogs.com/junyuhuang/p/4127095.html，
代码如下：
package com.qdcz.breadth.demo;
/** * * <p>Title: HuffmanCode</p> * <p>Description:哈弗曼算法实现类 * * <a href="http://www.cnblogs.com/hibernate3-example/archive/2010/05/15/2492730.html">借鉴资料</a></p> * <p>Company: 奇点创智</p> * <p>Version: 1.0</p> * @author Administrator * @date 2017年6月6日 下午7:29:41 */public class HuffmanCode { private int charAndWeight[][];// [][0]是 字符，[][1]存放的是字符的权值（次数 private int hfmcodeing[][];// 存放哈弗曼树 private int i=0;// 循环变量 private String hcs[]; public HuffmanCode(int[][] chars) { charAndWeight=new int[chars.length][2]; charAndWeight=chars; hfmcodeing=new int[2*chars.length-1][4];// 为哈弗曼树分配空间 } /** * *<p>Title: codeing</p> *<p>Description:哈夫曼树的实现 </p> *@return void *@author Administrator *@date 2017年6月6日 下午8:08:43 */ public void codeing(){ int n=charAndWeight.length; if(n==0) return; int m=2*n-1; //初始化哈弗曼树 for (int i = 0; i < n; i++) { hfmcodeing[i][0]=charAndWeight[i][1];// 初始化哈弗曼树的权值 hfmcodeing[i][1]=0;// 初始化哈弗曼树的根节点 hfmcodeing[i][2]=0;// 初始化哈弗曼树的左孩子 hfmcodeing[i][3]=0;// 初始化哈弗曼树的右孩子 } for (int i = 0; i <m; i++) { hfmcodeing[i][0]=0;// 初始化哈弗曼树权值 hfmcodeing[i][1]=0;// 初始化哈弗曼树的根节点 hfmcodeing[i][2]=0;// 初始化哈弗曼树的左孩子 hfmcodeing[i][3]=0;// 初始化哈弗曼树的右孩子 } //构建哈弗曼树 for (int i = n; i < m; i++) { int s[]=select(i);// 在哈弗曼树中查找双亲为零的 weight最小的节点 hfmcodeing[s[0]][1]=i;// 为哈弗曼树最小值付双亲 hfmcodeing[s[1]][1]=i; hfmcodeing[i][2]=s[0];// 新节点的左孩子 hfmcodeing[i][3]=s[1];// 新节点的右孩子 hfmcodeing[i][0]=hfmcodeing[s[0]][0]+hfmcodeing[s[1]][0];// 新节点的权值是左右孩子的权值之和 } } /** * *<p>Title:select </p> *<p>Description: 查找双亲为0的weight最小的节点</p> *@param w *@return *@return int[] *@author Administrator *@date 2017年6月6日 下午8:12:32 */ private int[] select(int w) { int[] s={-1,-1};// s1 最小权值且双亲为零的节点的序号 ， i 是循环变量 int j=0; int min=32767,min1=32767; for (int i = 0; i < w; i++) { if(hfmcodeing[i][0]==0){ // 只在尚未构造二叉树的结点中查找（双亲为零的节点） if(hfmcodeing[i][0]<min){ min1=min; s[1]=s[0]; min=hfmcodeing[i][0]; s[0]=i; }else if(hfmcodeing[i][0]<min1){ min1=hfmcodeing[i][0]; s[1]=i; } } } return s; } /** * *<p>Title:CreateHcode </p> *<p>Description:根据哈弗曼树求哈弗 编码</p> *@return *@return String[] *@author Administrator *@date 2017年6月6日 下午8:13:59 */ public String[] CreateHcode(){ int n=charAndWeight.length; int i,f,c; String hcodeing=""; hcs=new String[n]; for (int j = 0; j <n; j++) {//根据哈夫曼树求哈夫曼编码 c=j; hcodeing=" "; f=hfmcodeing[j][1];// f 哈弗曼树的根节点 while(f!=0){// 循序直到树根结点 if(hfmcodeing[f][2]==c){// 处理左孩子结点 hcodeing+="0"; }else{ hcodeing+="1"; } c=f; f=hfmcodeing[f][1]; } hcs[j]=new String(new StringBuffer(hcodeing).reverse()); } return hcs; } /** * *<p>Title: show</p> *<p>Description:对字符串显示编码 </p> *@param s *@return *@return String *@author Administrator *@date 2017年6月6日 下午8:15:59 */ public String show(String s){ String textString=""; char [] c; int k=-1; c=new char[s.length()]; c=s.toCharArray(); for (int i = 0; i < c.length; i++) { k=c[i]; for (int j = 0; j < charAndWeight.length; j++) { if(k==charAndWeight[j][0]) textString+=hcs[j]; } } return textString; } /** * *<p>Title: reCoding</p> *<p>Description: 哈弗曼编码反编译</p> *@param s *@return *@return String *@author Administrator *@date 2017年6月6日 下午8:16:29 */ public String reCoding(String s){ String text="";// 存放反编译后的字符 int k=0,m=hfmcodeing.length-1;// 从根节点开始查询 char c[]; c=new char[s.length()]; c=s.toCharArray(); k=m; for (int i = 0; i < c.length; i++) { if(c[i]=='0'){ k=hfmcodeing[k][2]; // k的值为根节点左孩子的序号 if(hfmcodeing[k][2]==0&&hfmcodeing[k][3]==0){// 判断是不是叶子节点，条件（左右孩子都为零） text+=charAndWeight[k][0]; k=m; } } if(c[i]=='1'){ k=hfmcodeing[k][3];// k的值为根节点右孩子的序号 if(hfmcodeing[k][2]==0&&hfmcodeing[k][3]==0){// 判断是不是叶子节点，条件（左右孩子都为零） text+=charAndWeight[k][0]; k=m; } } } return text; } public static void main(String[] args) { int[][] chars=new int[5][5]; String s="10101010110"; HuffmanCode code=new HuffmanCode(chars); code.codeing(); String ss[]=code.CreateHcode(); s=code.show(s); for (int i = 0; i < ss.length; i++) { System.out.println(ss[i].toString()); } }
}
转载于:https://www.cnblogs.com/1x-zfd50/p/6958961.html
