Huffman编码是之前一道算法作业题，最近又要复习考试了，先把这个的代码再看一下吧。
算法原理很简单，使用优先队列将两个节点弹出，然后合并节点之后再入队列如此循环做下去即可。
主要问题在于树的修改问题，出队的树进行修改，然后将其合并成为一个新的树，在弹出的时候，树的两个节点地址已定，但是由于循环这两个地址会进行修改，所以单独写了一个函数用来进行树的复制。
#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
#include<queue>
using namespace std;
typedef struct tree{
struct tree *left;
struct tree *right;
int data;
}Tree; struct cmp
{
bool operator()(const Tree &t1,const Tree &t2)
{
return t1.data>t2.data;
}
};
int a[]={,,,,,,,};//乱序
int code[]={};
int m=;
void printhuffman(Tree *huffman)
{
if(huffman->left!=NULL)
{
code[m]=;m++;
printhuffman(huffman->left);
m--;
}
if(huffman->right!=NULL)
{
code[m]=;m++;
printhuffman(huffman->right);
m--;
}
if(huffman->left==NULL&&huffman->right==NULL)
{
printf("The code of frequency is %3d :",huffman->data);
for(int i=;i<m;i++)
printf("%d ",code[i]);
printf("\n");
return ;
}
}
void copytree(Tree **a,Tree *b)
{
*a=new Tree();
if(b->left==NULL&&b->right==NULL)
{
(*a)->left=NULL;(*a)->right=NULL;
(*a)->data=b->data;
return;
}
if(b->left!=NULL)
{
(*a)->left=b->left;
copytree(&((*a)->left),b->left);
}
(*a)->data=b->data;
if(b->right!=NULL)
{
(*a)->right=b->right;
copytree(&((*a)->right),b->right);
} }
int main()
{
int n=;
priority_queue<Tree,vector<Tree>,cmp> minnode;
Tree huffman; for(int i=;i<n;i++)
{
Tree *newtree=new Tree();
newtree->data=a[i];
newtree->left=NULL;
newtree->right=NULL;
minnode.push(*newtree);
}
while(minnode.size()>=)
{
Tree temp1=minnode.top();minnode.pop();
Tree temp2=minnode.top();minnode.pop();
Tree *temp3=new Tree();
temp3->left=NULL;
temp3->right=NULL;
temp3->data=;
copytree(&temp3->left,&temp1);
copytree(&temp3->right,&temp2);
temp3->data=(*(temp3->left)).data+(*(temp3->right)).data;
minnode.push(*temp3);
}
huffman=minnode.top();
printhuffman(&huffman);
return ;
}
运行结果：
