java 哈夫曼编码

//哈夫曼树类
public class HaffmanTree {
//最大权值
static final int MAXVALUE=;
int nodeNum ; //叶子结点个数 public HaffmanTree(int n)
{
this.nodeNum = n;
} //构造哈夫曼树算法
public void haffman(int[] weight,HaffNode[] nodes)//权值数组，所有节点数组
{
int n = this.nodeNum;
//m1,m2,表示最小的两个权值，x1,x2,表示最小两个权值对应的编号,m1表示最小，m2表示次小
int m1,m2,x1,x2; //初始化所有的结点，对应有n个叶子结点的哈夫曼树，有2n-1个结点。
for(int i=;i < *n-;i++)
{
HaffNode temp = new HaffNode();
//初始化n个叶子结点，就是输入的节点。0、1、2、3是叶子节点也是输入的节点
if(i < n)
{
temp.weight = weight[i];
}
else
{
temp.weight = ;
}
temp.parent = ;
temp.flag = ;
temp.leftChild = -;
temp.rightChild = -;
nodes[i] = temp;
} for(int i=;i<n-;i++){//初始化n-1个非叶子结点，n-1表示要循环n-1次求的n-1个数。
m1 = m2 = MAXVALUE;
x1 = x2 =;
for(int j=;j< n+i;j++)//求得这n-1个数时，每次都是从0到n+i-1,并且flag=0的，flag=1表示已经加入到二叉树。
{ //以下2步是找出权值最小的2个
if(nodes[j].weight<m1 && nodes[j].flag==)//if成立了else、else if就不进去了。
{
//m1,x1初始值为第一个元素，后面如果比m1要小，则m1指向更小的，原来m1指向的现在由m2指向，
//如果后面比m1大比m2小，则m2指向这个比m1大比m2小的，
//也就是说m1指向最小的，m2指向第2小的。
m2 = m1;
x2 = x1;
m1 = nodes[j].weight;
x1 = j;
}
else if(nodes[j].weight<m2 && nodes[j].flag ==)
{
m2 = nodes[j].weight;
x2 = j;
}
}
//将权值最小的2个组合成一个2插树
nodes[x1].parent = n+i;
nodes[x2].parent = n+i;
nodes[x1].flag = ;
nodes[x2].flag = ;
nodes[n+i].weight = nodes[x1].weight + nodes[x2].weight;
nodes[n+i].leftChild = x1;
nodes[n+i].rightChild = x2;
}
/*
初始化数组之后：[1,3,5,7,4,9,16]
编码：100、101、11、0
*/
} //哈弗曼编码算法
public void haffmanCode(HaffNode[] nodes,Code[] haffCode)
{
int n = this.nodeNum;
Code code = new Code(n);//
int child,parent; for(int i=;i<n; i++)//给前面n个输入的节点进行编码
{
code.start = n-;//
code.weight = nodes[i].weight;//
child = i;//
parent = nodes[child].parent;
//从叶子节点向上走来生成编码，画图即可。
while(parent!=)
{
if(nodes[parent].leftChild == child)
{
code.bit[code.start] = ;
}
else
{
code.bit[code.start] = ;
} code.start--;
child = parent;
parent = nodes[child].parent;
} Code temp = new Code(n);
for(int j=code.start+;j < n;j++)
{
temp.bit[j] = code.bit[j];
}
temp.weight = code.weight;
temp.start = code.start;
haffCode[i] = temp;
}
}
}//哈夫曼树的结点类
public class HaffNode { int weight; //权值
int parent ;//他的双亲
int flag ;//标志，是否为叶子节点
int leftChild; //他的左孩子
int rightChild;//他的右孩子 HaffNode()
{ }}//哈夫曼编码类
public class Code { int[] bit; //编码的数组
int start; //编码的开始下标
int weight; //权值
Code(int n){
bit = new int[n];
start = n-;
}
}public class Test { public static void main(String[] args) { int n = ;
int[] weight = {,,,};
HaffmanTree haffTree = new HaffmanTree(n);
HaffNode[] nodes = new HaffNode[*n-];
Code[] codes = new Code[n];
//构造哈夫曼树
haffTree.haffman(weight, nodes);
//生成哈夫曼编码
haffTree.haffmanCode(nodes, codes); //打印哈夫曼编码
for(int i=;i<n;i++)
{
System.out.print("Weight="+codes[i].weight+" Code=");
for(int j=codes[i].start+;j<n;j++)
{
System.out.print(codes[i].bit[j]);
}
System.out.println();
}
}}