哈夫曼树的建立 一、 实验目的： 1． 理解哈夫曼树及其应用。 2． 掌握生成哈夫曼树的算法。 二、 实验内容： 哈夫曼树

数据结构实验十：哈夫曼树的建立 哈夫曼树的建立

一、 实验目的：

1．  理解哈夫曼树及其应用。

2．  掌握生成哈夫曼树的算法。

二、 实验内容：

哈夫曼树，即最优树，是带权路径长度最短的树。有着广泛的应用。在解决某些判定问题上，及字符编码上，有着重要的价值。

构造一棵哈夫曼树，哈夫曼最早给出了算法，称为哈夫曼算法：

（1）根据给定的N个权值   W1，W2，W3，……，Wn    ，构成N棵二叉树的集合F=     T1，T2，T3，……，Tn      ，其中每棵二叉树T1只有一个带权为WI的根结点，其左右子树均空。

（2）在 F中选出两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的权值为其左右子树上的根结点的权值之和。

（3）在F中删除这两棵树，同时将新得到的加到F之中。重复（2）和（3），直至F中只剩一个为止。

 

 



参考程序

#include"stdio.h"

#define LEN sizeof(struct HTnode)

int i,l,n,w=0,c,start,a1,a2,f;

struct HTnode {unsigned int weight;

       unsigned int parent,lchild,rchild;

      }*p,*HT;

typedef char **Huffmancode;

Huffmancode HC;

char *cd;

select()

{int k=1,j,flag=0;

 while((HT+k)->parent!=0) k++;

 for(j=k+1;j<=n;j++,flag=0)

  {if((HT+j)->parent!=0) flag=1;

   if((HT+j)->weight==0) flag=1;

   if(!flag) {if((HT+j)->weight<(HT+k)->weight) k=j;}

  }

 return(k);

}

main()

{printf("\n赫夫曼树的建立:\n");

 printf("请输入权值(叶子)数目:");

 scanf("%d",&l);

 while(l<1) {printf("输入错误,请重新输入权值数目:"); scanf("%d",&l); }

 if(l==1) printf("\n只有一个权值,无须建立赫夫曼树!");

 else {n=2*l-1;

       HT=(struct HTnode*)malloc((n+1)*LEN);

       printf("请按对应顺序输入权值(输入一权值,键入一回车):\n");

       for(i=1,p=HT+1;i<=l;++i,++p)

{scanf("%d",&w);

 while(w<=0){printf("权值错,重新输入此权值:"); scanf("%d",&w);}

 p->weight=w; p->parent=0;

 p->lchild=0; p->rchild=0;

}

      for(i=l+1;i<=n;++i,++p)

       {p->weight=0; p->parent=0;

p->lchild=0;

       }

      for(i=l+1;i<=n;++i)

       {a1=select(); (HT+a1)->parent=i;

a2=select(); (HT+a2)->parent=i;

       (HT+i)->lchild=a1;

       (HT+i)->rchild=a2;

       (HT+i)->weight=(HT+a1)->weight+(HT+a2)->weight;

       }

     HC=(Huffmancode)malloc((l+1)*sizeof(char *));

     cd=(char *)malloc(l*sizeof(char));

     *(cd+(l-1))='\0';

     for(i=1;i<=l;++i)

      {start=l-1;

       for(c=i,f=(HT+i)->parent;f!=0;c=f,f=(HT+f)->parent)

       if((HT+f)->lchild==c) *(cd+(--start))='0';

       else *(cd+(--start))='1';

      *(HC+i)=(char *)malloc((l-start)*sizeof(char));

      strcpy(*(HC+i),(cd+start));

     }

    printf("\n对应的二进制赫夫曼编码为:\n");

    for(i=1;i<=l;++i)

      {printf("%s",*(HC+i));

       printf("   ");

      }

 }

}