huffman哈弗曼编码的问题(java)

发布网友发布时间：2022-05-30 17:43

共2个回答

热心网友时间：2023-10-23 20:48

package Huffman;
public class HuffmanTree {
int leafNum; //叶子结点数
HuffmanNode[] hnodes; //HaffmanTree 的结点数组
public HuffmanTree(int[] weight){
int n=weight.length;
this.leafNum=n;
this.hnodes=new HuffmanNode[2*n-1];
for(int i=0;i<=n-1;i++)
{
this.hnodes[i]=new HuffmanNode(weight[i]);
}
for(int i=0;i<n-1;i++)
{
int min1,min2,x1,x2;
min1=min2=Integer.MAX_VALUE; //记录最小和次小的权值，初始为最大
x1=x2=-1; //记录两个无父母的最小权值的结点下标
for(int j=0;j<n+i;j++)
{
//查找无父母的最小权值结点
if(this.hnodes[j].weight<min1 && this.hnodes[j].parent==-1)
{
min2=min1;
x2=x1;
min1=this.hnodes[j].weight;
x1=j;
}
else if(this.hnodes[j].weight<min2 && this.hnodes[j].parent==-1)
{
min2=this.hnodes[j].weight;
x2=j;
}
}
this.hnodes[x1].parent=n+i; //将找出的两课权值最小的二叉树合并
this.hnodes[x2].parent=n+i;
this.hnodes[n+i]=new HuffmanNode(0);
this.hnodes[n+i].weight=this.hnodes[x1].weight+this.hnodes[x2].weight;
this.hnodes[n+i].left=x1;
this.hnodes[n+i].right=x2;
}
}
public String[] huffmanCode(){
//返回当前haffmantree的编码
String[] code=new String[this.leafNum];
for(int i=0;i<this.leafNum;i++)
{
code[i]="";
int child=i;
int parent=hnodes[child].parent;
while(parent!=-1)
{
if(hnodes[parent].left==child)
code[i]="0"+code[i];
else
code[i]="1"+code[i];
child=parent;
parent=hnodes[child].parent;
}
}
return code;
}
public static void main(String []args)
{
int[] weight={22,32,45,57,7,76,33};
HuffmanTree ht=new HuffmanTree(weight);
String[] code=ht.huffmanCode();
for(int i=0;i<code.length;i++)
System.out.println(weight[i]+" 哈夫曼编码为： "+code[i]);
}
}
改了其中的几个for循环条件可以运行了

热心网友时间：2023-10-23 20:49

package Huffman;
class HuffmanNode{
int weight; //权
int parent,left,right; //父母结点，左右孩子下标

public HuffmanNode(int weight){
this.weight=weight;
this.parent=this.left=this.right=-1;
}
}
public class HuffmanTree {
int leafNum; //叶子结点数
HuffmanNode[] hnodes; //HaffmanTree 的结点数组

public HuffmanTree(int[] weight){
int n=weight.length;
this.leafNum=n;
this.hnodes=new HuffmanNode[2*n-1];
for(int i=0;i<n-1;i++){
this.hnodes[i]=new HuffmanNode(weight[i]);
}
for(int i=0;i<n-1;i++){
int min1,min2,x1,x2;
min1=min2=Integer.MAX_VALUE; //记录最小和次小的权值，初始为最大
x1=x2=-1; //记录两个无父母的最小权值的结点下标
for(int j=0;j<n+i;j++){ //查找无父母的最小权值结点
if(hnodes[j].weight<min1 && hnodes[j].parent==-1){
min2=min1;
x2=x1;
min1=hnodes[j].weight;
x1=j;
}
else if(hnodes[j].weight<min2 && hnodes[j].parent==-1){
min2=hnodes[j].weight;
x2=j;
}
}
hnodes[x1].parent=n+i; //将找出的两课权值最小的二叉树合并
hnodes[x2].parent=n+i;
this.hnodes[n+i]=new HuffmanNode(0);
hnodes[n+i].weight=hnodes[x1].weight+hnodes[x2].weight;
hnodes[n+i].left=x1;
hnodes[n+i].right=x2;

}
}
public String[] huffmanCode(){ //返回当前haffmantree的编码
String[] code=new String[this.leafNum];
for(int i=0;i<this.leafNum;i++){
code[i]="";
int child=i;
int parent=hnodes[child].parent;
while(parent!=-1){
if(hnodes[parent].left==child)
code[i]="0"+code[i];
else
code[i]="1"+code[i];
child=parent;
parent=hnodes[child].parent;
}
}
return code;
}
public static void main(String []args){
int[] weight={22,32,45,57,7,76,33};
HuffmanTree ht=new HuffmanTree(weight);
String[] code=ht.huffmanCode();
for(int i=0;i<code.length;i++)
System.out.println(weight[i]+" 哈夫曼编码为： "+code[i]);
}
}
运行后
Exception in thread "main" java.lang.NullPointerException
at ht.binary.main(binary.java:90)