《哈夫曼树的建立与操作》由会员分享，可在线阅读，更多相关《哈夫曼树的建立与操作（4页珍藏版）》请在金锄头文库上搜索。
1、实验六哈夫曼树的建立与操作一、实验要求和实验内容1、输入哈夫曼树叶子结点（信息和权值）2、由叶子结点生成哈夫曼树内部结点3、生成叶子结点的哈夫曼编码4、显示哈夫曼树结点顺序表二、详细代码（内包含了详细的注释）:#includeviostreamusing namespace std;typedef char Elemtype;struct elementint weight;Elemtype date;element* lchild,*rchild;class HuffmanTreepublic:HuffmanTree()构造函数coutvv请输入二叉树的个数vvendl;cincount;e
2、lement *s=new elementcount;/s为指向数组的指针，保存指向数组的地址for(int i=0;ivcount;i+)coutvv输入第vvi+1vv个节点的权值vvendl;cinsi.weight;coutvv输入第vvi+lvv个节点的内容vvendl;cinsi.date; si.lchild=NULL; si.rchild=NULL;以上为初始化每一个结点element * *m=new element*count;/m为指向数组成员的地址的指针，保存【指向 数组成员地址的指针】的地址for(int i=0;icount;i+)mi=s+i;把数组成员i地址赋给
3、mi (mi大致意思等效于*m)以下为哈夫曼的构造过程element*q;for(int i=0;ivcount-1;i+)int a=32767,b=32767;/a,b为两个存当前最小值的两个临时变量，初始化为 32767(int型能达到的最大的值)for(int i=1;iweightweight;return1=i;for(int i=0;iweightweighta)b=mi-weight;return2=i;q=new element;/构建一棵新树 q-weight=mreturn1-weight+mreturn2-weight; q-lchild=mreturn1;q-rchi
4、ld=mreturn2;mreturn1=q;mreturn2=NULL;用新树替换原来的两子树，并置空一个数boot=q;把最后取得的哈夫曼树的头结点即q赋值给boot coutvv哈夫曼树构造成功vvendl;void HufumanCoding(element* bt,int len=0)求哈夫曼编码,len为哈夫曼编码的位数默认 为0if(bt)当bt不为空时进入if(!bt-lchild& !bt-rchild)当此结点为叶子结点时进入coutvv权值为vcbt-Adatevv结点的哈夫曼编码为：;for(int i=0;ivlen;i+)coutvvmi;coutvvendl;elsemlen=0; HufumanCoding(bt-lchild,len+l);mlen=1; HufumanCoding(bt-rchild,len+1);element* ReturnBoot()return boot;private:int count;/ 结点数int return1,return2;权值最小的节点的在数组中的位置element* boot;int m20;存储哈夫曼编码;int main()element* m;HuffmanTree a;m=a.ReturnBoot();a.HufumanCoding(m);三、运行结果
