哈夫曼树的建立与操作

1、实验六哈夫曼树的建立与操作一、实验要求和实验内容1输入哈夫曼树叶子结点(信息和权值)2、由叶子结点生成哈夫曼树内部结点3、生成叶子结点的哈夫曼编码4、显示哈夫曼树结点顺序表二、 详细代码(内包含了详细的注释)：#in cludeusing n amespace std;typedef char Elemtype;struct eleme ntint weight;Elemtype date;eleme nt* lchild,*rchild;class Huffma nTreepublic:HuffmanTree() 构造函数cout请输入二叉树的个数 co unt;element *s=new

2、 elementcount;/s为指向数组的指针，保存指向数组的地址 for(i nt i=0;ico un t;i+)cout输入第i+1个节点的权值 si.weight;cout输入第i+1个节点的内容 si.date;sichild=NULL;si.rchild=NULL;/以上为初始化每一个结点eleme nt * *m=n ew eleme nt*cou nt;/m为指向数组成员的地址的指针，保存【指向数组成员地址的指针】的地址for(i nt i=0;ico un t;i+)mi=s+i;把数组成员i地址赋给mi ( mi大致意思等效于*m)以下为哈夫曼的构造过程eleme nt*

3、q;for(i nt i=0;ico un t-1;i+)int a=32767,b=32767;/a,b为两个存当前最小值的两个临时变量，初始化为 32767( int型能达到的最大的值)for(i nt i=1;iweightweight;return仁i;for(i nt i=0;iweightweighta)b=mi-weight;return2=i;q=new eleme nt;构建一棵新树q-weight=mreturn1-weight+mreturn2-weight;q-lchild=mretur n1;q-rchild=mreturn2;mreturn1=q;mreturn2=

4、NULL;/用新树替换原来的两子树，并置空一个数boot=q;/把最后取得的哈夫曼树的头结点即q赋值给bootcout哈夫曼树构造成功lchild&!bt-rchild)当此结点为叶子结点时进入cout权值为date结点的哈夫曼编码为：;for(i nt i=0;ile n; i+)coutmi;coutlchild,le n+1);mle n=1; Hufuma nCodi ng(bt-rchild,le n+1);eleme nt* ReturnBoot()return boot;private:int count;/ 结点数int return1,return2;权值最小的节点的在数组中的位置eleme nt* boot;int m20;/存储哈夫曼编码;int mai n()eleme nt* m;Huffma nTree a;m=a.ReturnBoot();a.Hufuma nCodi ng(m);三、运行结果QBC:WI N DOWSsystem 3 2c md.exe为为为为3 马 ripriprim I-串帀帀帀5 二冊” n冊.-n冊IJ冊 &. 曼曼曼曼晏- r瞻璧 .蜚点占苦 忡士 口士口吉吉士口歿 %$d&壽矗章 为为为为韋16901SB11B1育输人二叉树的个数 矗心丄个节点的杈值 書入第丄个节点的内容 仞入第去个节点