这是我自己实现的霍夫曼树，我觉得大家需要注意的最主要的问题就是使用优先队列的话，你每往里面插入一个对象的话就会生成一个新的对象这个时候你的地址就发生变化了，所以我直接开了一个全局变量的element的数组，然后每一个element直接保存了自身的地址，这让你插入优先队列的话就不会发生问题了，就算插入之后地址发生了变化，但是你有myself这个指针保存着自身的地址，所以说，当两个节点需要合并的时候，就可以解决地址发生变化的问题了。
#include<iostream>
using namespace std;
#include<stdio.h>
#include<queue>
#include<string.h>
class element//这个是对元素定义
{
public:
char ch;
element *left;
element *right;
element *myself;
int weight;
int code[20];
int index;
element()
{
ch='\0';
index=0;//下标
memset(code,0,sizeof(code));//这个就是让他的标志为全部为0
left=NULL;
right=NULL;
myself=NULL;//用以记录本身的地址。
}
void SetV(char ch1,int w)
{
ch=ch1;
left=NULL;
right=NULL;
myself=NULL;
weight=w;
}
friend bool operator<(const element &e1,const element &e2)
{
return e1.weight>e2.weight;
}
};
priority_queue<element> myQ;
element Wow[100];
void StoreNode(int n)//存储所有的节点,bingo!!!!
{
while(!myQ.empty())
{
myQ.pop();
}
for(int i=1;i<=n;i++)//将element数组修改值
{
//生成一个元素
char a,b,c;
int we;
scanf("%c%c%d%c",&a,&c,&we,&b);
Wow[i].SetV(a,we);//这样就已经对每个点都进行了赋值
Wow[i].myself=&Wow[i];//将Wow[i]的地址保存在自己的myself当中
myQ.push(Wow[i]);
}
}
void Codeit(element *e,int value) //not bingo
{
if(e==NULL)
{
return;
}
if(e->left==NULL&&e->right==NULL)//代表的意思就是如果是叶子节点，就果断的将其code赋值
{
e->code[e->index]=value;
e->index++;
}
else //如果不是叶子节点的话，那么就应该
{
Codeit(e->left,value);
Codeit(e->right,value);
}
}
void visit(element *e)// bingo?
{
if(e==NULL)
{
return;
}
if(e->left==NULL&&e->right==NULL)//叶子节点
{
printf("%c's code is:\n",e->ch);
for(int i=e->index-1;i>=0;i--)
{
printf("%d",e->code[i]);
}
printf("\n");
}
visit(e->left);
visit(e->right);
}
void Huffman(int n)//构建霍夫曼树的过程
{
StoreNode(n);
for(int i=n+1;i<=2*n-1;i++)//弹出来的两个树他们的码是0是1是没关系的
{
element e1,e2;//新建立的保存在数组当中
e1=myQ.top();
myQ.pop();
e2=myQ.top();
myQ.pop();
Wow[i].weight=e1.weight+e2.weight;
Wow[i].left=e1.myself;
Wow[i].right=e2.myself;
Wow[i].myself=&Wow[i];//保存下这个element对象本身的地址
Codeit(e1.myself,0);
Codeit(e2.myself,1);
myQ.push(Wow[i]);
}//最后就只剩下一个元素
element e=myQ.top();
myQ.pop();
visit(e.myself);
}
int main()
{
int n;
char c;
scanf("%d%c",&n,&c);
Huffman(n);
return 0;
}
