7、是将这些结点加入到二叉树中 ， 构建成哈夫曼树 。
1、 在所有结点中选出权值最小的两个结点 。
、选择权值最小的两个结点并不难 ， 难在如何判断该结点是否已经使用过 ， 若不能正确判断前面构造的哈夫曼树中是否使用过该结点 ， 可能造成结点重复出现在树中 ， 出现错误 。
根据哈夫曼树构造的特点 ， 当两个结点的权值为最小时就将做为新的二叉树的左（右）子树 ， 而它们的权值之和为它们的根结点 ， 所以可以通过判断该结点是否有父亲结点来判断它是否被使用过 。
if(HTi.parent=0) /*没有父亲结点说明该 结点还未被使用过*/min=HTi.weight;
/*给min赋初始值*/s1=i;
/*将结点的编号赋给s1*/break;
。

8、 tempi=i+;
/*i确定下一个结点的编号*/、然后利用数字排序的方法 ， 对符合要求的结点进行判断 ， 当存在权值更小的结点是 ， 将该结点的内容赋给min和s1.for(;
is2) temp=s1;
s1=s2;
s2=temp;
code.s1=s1;
code.s2=s2;
return code;
2、 将选择出来的结点一个个逐步构建成哈夫曼树 。
、哈夫曼树实现的功能就是将若干个结点以最优化的顺序排列出来 ， 所以当结点数n=1时 ， 不存在构建哈夫曼树的问题 。
因此 ， 首先对可能出现的这种状况进行判断 。
if(nweight=*w;
p-parent=0;
/*给待处理的结点赋予权值 ， 父p-lchild= 。

9、0;
亲、左孩子、右孩子均赋0值*/p-rchild=0;
for(;
iweight=0;
p-parent=0;
/*对待构建的哈夫曼树p-lchild=0;
的编码进行初始化*/p-rchild=0;
、构建哈夫曼树 ， 通过Select函数选择还未被使用的且权值为最小的两个结点 ， 将其加入到树中 。
for(i=n+1;
i=m;
i+) min=Select(HT,i-1);
s1=min.s1;
/*s1、s2分别存权值最小s2=min.s2;
的两个结点的编号*/HTs1.parent=i;
HTs2.parent=i;
HTi.lchild=s1;
HTi.rchild=s2;
HTi.wei 。

10、ght=HTs1.weight+HTs2.weight;
、构建完成哈夫曼树后 ， 为知道每个结点的具体编码 ， 必须对哈夫曼树进行遍历 ， 且必须从叶子结点向根结点逆序进行遍历 。
HC=(HuffmanCode)malloc(n+1)*sizeof(char *);
cd=(char *)malloc(n*sizeof(char *);
/*分配求编码的工作空间*/cdn-1=0;
/*编码结束符*/for(i=1;
i=n;
i+) /*逐个字符求赫夫曼编码*/ start=n-1;
/*编码结束符位置*/for(c=i,f=HTi.parent;
f!=0;
c=f,f=HTf.parent) /*从叶子到根 。

11、逆向求每个 if(HTf.lchild=c) 字符的赫夫曼编码*/ cd-start=0;
/*左孩子赋0值*/else cd-start=1;
/*右孩子赋1值*/ 3、输出的设置由于哈夫曼树的树形结构比较难在计算机屏幕上实现 ， 而又需要明确的表示出每个结点在树中的位置 ， 所以对输出采取了以下两种样式 。
、输出每个结点的父亲、左孩子、右孩子结点的编号 ， 从而确定每个结点的具体位置 。
由于在构建哈夫曼树的Create函数中已经完成了每个结点的父亲、左孩子、右孩子结点的赋值 ， 所以只需要将这些值直接输出即可 。
printf(HT List:n);
printf(Numberttweightttparenttt 。

12、lchildttrchildn);
for(i=1;
i=m;
i+) printf(%dtt%dtt%dtt%dtt%dn, i,HTi.weight,HTi.parent,HTi.lchild,HTi.rchild);
、哈夫曼树的功能是将每个结点用0和1表示出来 ， 所以将每个结点的哈夫曼编码表示出来也可以确定哈夫曼树的结构 。
而在Create函数中 ， 同样已经给确定了结点的0值和1值 ， 只需要调用一个字符串函数将每个结点的编码复制到该结点相应的编码值Code中 。
然后再在主函数中将其打印出来 。
HCi=(char *)malloc(n-start)*sizeof(char *);
/*为第i个字符编码分配 。

13、空间*/strcpy(HCi,&cdstart);
/*从cd复制编码（串）到HC*/printf(HuffmanCode:n);
printf(NumberttWeightttCoden);
for(i=1;
i=n;
i+) printf(%dtt%dtt%sn,i,wi,HCi);
五、流程图main函数： Select函数：CreatTree函数：六、实验结果演示1、当输入的结点个数n2时：2、当输入的结点数n=1时 ， 不存在构建哈夫曼树的问题 ， 输出错误提示：七、在编写程序过程中遇到的困难和解决的方法数据结构上机实验是使我们进一步掌握和深化所学知识的必不可少的内容之一 ， 是后继专业课程的基础 ，。

14、是培养我们综合能力和提高我们科学素养的必不可少的部分 ， 所以我对每次实验都抱以极其认真的态度 。
在刚开始拿到程序的题目时 ， 不知道从何入手 ， 因为题目表现的比较抽象 ， 并且自己在写哈夫曼树的过程中都遇到一些困难 ， 所以感觉很难完成 。

来源：(未知)

【学习资料】网址：/a/2021/0318/0021711234.html

标题：哈夫曼|哈夫曼编码实验报告( 二 )