赫夫曼树编码的实现（无栈非递归遍历）
#include<stdio.h>#include<stdlib.h>
#include<string.h>
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
void Select(HuffmanTree HT, int u, int &s1, int &s2) {
int j;
j=1;
while(j<=u && HT[j].parent!=0) j++;
s1=j;
while(j<=u) {
if(HT[j].parent==0 && HT[j].weight<HT[s1].weight) s1=j;
j++;
}
HT[s1].parent = u+1;
j = 1;
while(j<=u && HT[j].parent!=0) j++;
s2 = j;
while(j<=u) {
if(HT[j].parent==0 && HT[j].weight<HT[s2].weight) s2=j;
j++;
}
if (s1>s2) {
j=s1; s1=s2; s2=j;
}
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n){
int m,i,s1,s2,cdlen,p;
char *cd;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(i=1;i<=n;i++){
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(;i<=m;i++){
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(i=n+1;i<=m;i++){
Select(HT,i-1,s1,s2);
HT[s1].parent=i;HT[s2].parent=i;
HT[i].lchild=s1;HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
cd=(char *)malloc(n*sizeof(char));
p=m;
cdlen=0;
for(i=1;i<=m;i++) HT[i].weight=0;
while(p){
if(HT[p].weight==0){
HT[p].weight=1;
if(HT[p].lchild!=0) {p=HT[p].lchild;cd[cdlen++]='0';}
else if(HT[p].rchild==0){
HC[p]=(char *)malloc((cdlen+1)*sizeof(char));
cd[cdlen]='\0';
strcpy(HC[p],cd);
}
}
else if(HT[p].weight==1){
HT[p].weight=2;
if(HT[p].rchild!=0){
p=HT[p].rchild;
cd[cdlen++]='1';
}
}
else{
HT[p].weight=0;p=HT[p].parent;--cdlen;
}
}
free(cd);
}
void printHuffman(HuffmanTree HT,int n){
int k;
printf(" 结点 weight parent lchild rchild\n");
for(k=1;k<=2*n-1;k++){
printf("%4d",k);printf("%8d",HT[k].weight);
printf("%8d",HT[k].parent);printf("%8d",HT[k].lchild);printf("%8d",HT[k].rchild);
printf("\n");
}
}
void printHuffmanCode(HuffmanCode HC,int n,int *w){
int k,m;
for(k=1;k<=n;k++){
printf("频率为%d的编码:%d—>",w[k-1],k);
puts(HC[k]);
}
}
void main() {
int w[]={7,19,2,6,32,3,21,10},n=8;
HuffmanTree HT;
HuffmanCode HC;
HuffmanCoding(HT,HC,w,n);
printf("建立赫夫曼树:\n");
printHuffman(HT,n);
printf("无栈非递归遍历赫夫曼树:\n");
printHuffmanCode(HC,n,w);
}
