树和二叉树的建立和遍历-数据结构试验报告

1、实验报告一：预习要求预习树和二叉树的存储结构、以递归为基本思想的相应遍历操作。二：实验目的1、通过实验，掌握二叉树的建立与存储方法。2、掌握二叉树的结构特性，以及各种存储结构的特点和适用范围。3、掌握用指针类型描述、访问和处理二叉树的运算。4、理解 huffman 编解码的算法 三：实验内容 以括号表示法输入一棵二叉树， 编写算法建立二叉树的二叉链表结构； 编写先序、 中序、后序、层次遍历二叉树的算法；编写算法计算二叉树的结点数，叶子结点 数，以及二叉树的深度。四: 实验原理及试验方法ADT BinaryTree 数据对象 ：D ：D 是具有相同特征的数据元素的集合数据结构 ：R：若D=空集，

2、则R=空集，称BinaryTree为空二叉树；若D不等于空集，则R=H, H是如下二元关系：(1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2) 若D-root不等于空集，则存在 D-root=D1,Dr, 且Din Dr=空集；(3) 若D1不等于空集，则D1中存在唯一的元素x1，<root,x1> H,且存 在D1上的关系H1包含于H;若DrM空集，贝U Dr中存在唯一的元素 xr,<root,xr> H ， 且 存 在 Dr 上 的 关 系 Hr 包 含 于 H ； H=<root,x1>,<root,xr>,H1,

3、Hr;(4) (D1,H1) 是一颗符合本定义的二叉树，称为根的左子树，( Dr,Hr ) 是一颗符合本定义的二叉树，称为根的右子树 。基本操作 P：CreateBiTree(&T,definition);初始条件： definition 给出二叉树的定义。 操作结果：按 definition 构造二叉树 T。PreOrderTraverse(T);初始条件：二叉树T存在。操作结果：先序遍历 T 。InOrderTraverse(T);初始条件：二叉树T存在。操作结果：中序遍历 T。PostOrderTraverse（T）; 初始条件：二叉树 T 存在。 操作结果：后序遍历 T。Gua

4、ngYi（T）; 初始条件：二叉树 T 存在。 操作结果：广义表遍历。 PreThreading（T） 初始条件：二叉树 T 存在。 操作结果：二叉树先序线索化。 PreOrderThreading （ Thrt,T ） 初始条件：二叉树 T 存在。 操作结果：先序遍历二叉树将二叉树线索化。 PreOrderThread（T） 初始条件： T 存在。 操作结果：将先序线索化的二叉树输出。 InThreading（T） 初始条件： T 存在。 操作结果：二叉树中序线索化。 InOrderThreading （Thrt,T ） 初始条件： T 存在。 操作结果：中序遍历二叉树将二叉树线索化。 In

5、OrderThread （T） 初始条件： T 存在。 操作结果：将中序线索化的二叉树输出。 PostOrderThreading （T） 初始条件： T 存在。操作结果：二叉树的后序遍历。 PostThreading （Thrt,T ） 初始条件： T 存在。 操作结果：后序遍历二叉树并将其线索化。PostOrderThread （T） 初始条件： T 存在。 操作结果：将后序线索化的二叉树输出。 HuffmanCoding（HT,HC,n） 初始条件：HT, HC存在。操作结果：构造赫夫曼树HT,并将赫夫曼译码保存在 HC Select（HT,n,s1,s2） 初始条件：HT存在。操作结果

6、：用si和s2返回HT中权值最小的两个字符。 ADTBinaryTree 线索二叉树结构体： #include<stdio.h> typedef struct tree / 树的结构体定义char data; /存储类型 int ltag,rtag;/判断结点是的左、右孩子指针的指向变量，/ ltag=0 表示该结点有左孩子且 lchild 指向左孩子， ltag=1 表示该结点的 lchild 指向该结 点的前驱/rtag=0 表示该结点有右孩子且 rchild 指向右孩子， rtag=1 表示该结点的 rchild 指向该结 点的后继struct tree *lchild,*r

7、child;/结点的左、右孩子指针bit,*Bit;构造一个二叉树：Bit CreateBiTree(Bit T)/用先序遍历构建一个二叉树char ch;ch=getchar(); / 从刚在内存中输入的字符窜中依次获得字符 if(ch='#') / 判断接受字符是否表示空T=NULL;/指针为空else T=(bit *)malloc(sizeof(bit);/ 向内存中申请一个结点T->data=ch;/ 对结点进行字符赋值T->ltag=O;/初始化Itag和rtag,让他们的初值都为0T->rtag=0;T->lchild=CreateBiTr

8、ee(T->lchild); / 构建结点的左孩子 T->rchild=CreateBiTree(T->rchild); / 构建结点的右孩子 return T; /返回结点的地址 二叉树的先序遍历： void PreOrderTraverse(Bit T)/先序遍历if(T) printf("%c",T->data); /遍历根结点 PreOrderTraverse(T->lchild);/遍历左孩子PreOrderTraverse(T->rchild);/ 遍历右孩子 二叉树的广义表遍历： void GuangYi(Bit T)/广义

9、表遍历if(T)/判断结点的左右孩子都是否为空if(T->lchild=NULL && T->rchild=NULL) printf("%c",T->data);/ 都为空时，输出结点字符else /至少有一个不为空时 printf("(%c",T->data);/ 输出结点的字符 if(T->lchild)printf(",");GuangYi(T->lchild);/ 判断结点的左孩子是否为空， 不为 空时，递归的调用 GuangYi 函数if(T->rchild)prin

10、tf(",");GuangYi(T->rchild);printf(")");/ 判断结点的右孩子是否 为空，不为空时，递归的调用 GuangYi 函数else printf(")"); / 否则输出) 二叉树的先序线索化： void PreThreading(Bit p)/先序线索化if(p) / 判断结点是否为空 if(!p->lchild)p->ltag=1;p->lchild=pre;/前驱线索if(!pre->rchild)pre->rtag=1;pre->rchild=p;/后继线

11、索pre=p;/保持 pre 指向 p 的前驱if(p->ltag=0)PreThreading(p->lchild);/ 左子树线索化 if(p->rtag=0)PreThreading(p->rchild); / 右子树线索化Bit PreOrderThreading(Bit Thrt,Bit T) 先序遍历二叉树 T,并将其线索化，Thrt指向头结点并 返回到主函数中Thrt=(Bit)malloc(sizeof(bit);/ 相内存中申请结点Thrt->data='#'/头指针内容为空Thrt->ltag=0;Thrt->rta

12、g=1; /建立头结点Thrt->rchild=Thrt;/ 右指针回指if(!T)/ 若二叉树为空，则左指针回指Thrt->lchild=Thrt;else Thrt->lchild=T;pre=Thrt;PreThreading(T);/先序遍历进行先序线索化pre->rchild=Thrt;pre->rtag=1;/ 最后一个结点的线索化 Thrt->rchild=NULL; return Thrt; 先序二叉树的还原： int ReturnTree(Bit T) if(T->ltag=0)ReturnTree(T->lchild);/ 遍

13、历左子树 ,找到 ltag=1 的结点 else T->lchild=NULL;/令左指针指向空if(T->rtag=0)ReturnTree(T->rchild);/ 遍历右子树，找到 rtag=1 的结点 else T->rchild=NULL;/ 令右指针指向空7、树的清空：int CleanTree(Bit T)/ 树的清空if(T) if(T->lchild)CleanTree(T->lchild); if(T->rchild)CleanTree(T->rchild); free(T); 赫夫曼树的结构体： typedef struct

14、 / 赫夫曼编码结构体 char ch; / 编码存储类型 unsigned int weight;/ 权值 unsigned int parent,lchild,rchild; / 双亲、左孩子、右孩子HTNode,*HuffmanTree;typedef char *HuffmanCode;/ 动态分配数组存储赫夫曼编码两个权值最小字符的寻找：int Select(HuffmanTree HT,int n,int *s1,int *s2) / 在赫夫曼树中选取两个双亲为零且权值最 小的两个节点，用 s1、s2 返回int i,j; for(j=1;j<=n;+j) if(HTj.pa

15、rent=0) /选取第一个双亲不为零的结点赋值给 s1*s1=j; break; for(i=j+1;i<=n;+i) if(HTi.weight<HT*s1.weight&&HTi.parent=0)/ 选出权值最小的节点*s1=i;for(j=1;j<=n;+j) / 选出双亲为零且不是 s1 的结点 if(HTj.parent=0&&*s1!=j)*s2=j;break;for(i=j+1;i<=n;+i) if(HTi.weight<HT*s2.weight&&HTi.parent=0&&*

16、s1!=i) / 选出权值次小的节 点八、*s2=i;if(*s2<*s1) / 判断两个权值的大小是否符合要求，不符合交换i=*s1;*s1=*s2;*s2=i;赫夫曼编码：void HuffmanCoding(HuffmanTree HT,HuffmanCode *HC,int n)/构造赫夫曼树 HT ，并求出赫夫曼树所对应的的赫夫曼编码int i,j,f,m,c,start;int S1,S2;char *cd;m=n*2;for(i=1;i<=n;i+)/初始构造赫夫曼树printf(" 请输入第 %d 个字符和字符对应权值(中间用空格隔开，如：g 29)： &

17、quot;,i);scanf("%s %d",&HTi.ch,&HTi.weight);HTi.parent=0; /双亲和左右孩子均初始化为 0；HTi.lchild=0;HTi.rchild=0;for(;i<m;i+) / 将没有存放字符的结点权值、双亲和左右孩子均初始化为0HTi.weight=0; HTi.lchild=0; HTi.rchild=0;HTi.parent=0; for(i=n+1;i<m;i+)Select(HT,i-1,&S1,&S2);/ 从结点中选取两个最小的结点 HTS1.parent=i;HT

18、S2.parent=i; / 将新结点的位置的值赋给最小的两个结点的双 亲HTi.lchild=S1;HTi.rchild=S2; / 将最小的两个结点的位置的值赋给新结点的左 右孩子HTi.weight=HTS1.weight+HTS2.weight;/将两个最小结点的权值相加赋新结点的权值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;

19、c=f,f=HTf.parent)/ 从叶子到根逆向求编码if(HTf.lchild=c)cd-start='0' / 判断 c 是结点的那个孩子，左孩子添加 0， 右孩子添加 1else cd-start='1'HCi=(char *)malloc(n-start)*sizeof(char);/ 向内存中申请第 i 个字符编码分配空间 strcpy(HCi,&cdstart); /从 cd 复制编码串到 HCprintf(" 字符 译码 n");for(i=1;i<=n;i+) /显示译码printf("%5c %s

20、n",HTi.ch,HCi);free(cd);/ 释放空间六、思考题：1. 输入进行编码的字符串2. 遍历字符串，并为叶子节点权重赋值3. 依次对各字符进行哈弗曼编码， 自下往上，若是双亲节点左孩子则编码前插入 0'，若是双亲节点右孩子则编码钱插入 1'。4. 显示各字符的哈弗曼编码。5. 对字符串进行编码，挨个遍历字符，找到相应的编码，复制到总的编码里，最 后输出字符串的编码。6. 对字符串的哈弗曼码进行译码。自上往下，若是 0'，则递归到左孩子，若是1'，则递归到右孩子，知道叶子节点，输出该叶子节点代表字符，再继续 遍历。7. 分析内存占用情况。

21、若用 ASCII 编码，每个字符占 1 个字节，即 8bit ，该情 况下占用内存就是 (字符长度) *8。若用哈弗曼编码， 占用内存是各(字符频度) * (每个字符占用位数)之和。七：参考文献：1. C语言入门经典(第5版)作者：(美)霍尔顿(Horton,l.)著，杨浩译， 清华大学出版社， 2013年 11 月2. 数据结构( C 语言版)，严蔚敏，吴伟民编著，清华大学出版社， 2011 年 11 月3数据结构(C语言版)(第2版)，严蔚敏，李冬梅，吴伟民编著，人民 邮电出版社， 2015年 2月八：源代码：1、二叉树：#include<stdio.h>typedef str

22、uct tree /树的结构体定义char data;/ 存储类型int ltag,rtag;/判断结点是的左、右孩子指针的指向变量，/ ltag=0 表示该结点有左孩子且 lchild 指向左孩子， ltag=1 表示该结点的 lchild 指向该结点的前驱/rtag=0 表示该结点有右孩子且 rchild 指向右孩子， rtag=1 表示该结点的 rchild 指向该结点的后继struct tree *lchild,*rchild;/结点的左、右孩子指针bit,*Bit;Bit CreateBiTree(Bit T) / 用先序遍历构建一个二叉树char ch;ch=getchar();/

23、从刚在内存中输入的字符窜中依次获得字符if(ch='#') /判断接受字符是否表示空T=NULL; /指针为空else T=(bit *)malloc(sizeof(bit);/向内存中申请一个结点T->data=ch;/对结点进行字符赋值T->ltag=0;/初始化Itag和rtag,让他们的初值都为0T->rtag=0;T->lchild=CreateBiTree(T->lchild); /构建结点的左孩子 T->rchild=CreateBiTree(T->rchild); /构建结点的右孩子return T; /返回结点的地址/

24、二叉树的递归遍历 void PreOrderTraverse(Bit T) / 先序遍历if(T) printf("%c",T->data); / 遍历根结点 PreOrderTraverse(T->lchild); /遍历左孩子 PreOrderTraverse(T->rchild);/ 遍历右孩子void InOrderTraverse(Bit T) / 中序遍历if(T)In OrderTraverse(T->lchild);遍历左孩子prin tf("%c",T->data); 遍历根结点In OrderTraver

25、se(T->rchild);/遍 历右孩子void PostOrderTraverse(Bit T) /后序遍历if(T)PostOrderTraverse(T->lchild);/遍 历左孩子 PostOrderTraverse(T->rchild);/遍历右孩子 prin tf("%c",T->data);/ 遍历根结点void GuangYi(Bit T)/广义表遍历if(T)if(T->lchild=NULL && T->rchild=NULL)/判断结点的左右孩子都是否为空prin tf("%c&quo

26、t;,T->data);/都为空时，输出结点字符else/至少有一个不为空时prin tf("(%c",T->data);/ 输出结点的字符 if(T->lchild)printf(",");GuangYi(T->lchild);/ 判断结点的左孩子是否 为空，不为空时，递归的调用 GuangYi 函数if(T->rchild)printf(",");GuangYi(T->rchild);printf(")");/ 判 断 结 点 的 右孩子是否为空，不为空时，递归的调用 Gua

27、ngYi 函数else printf(")"); / 否则输出)/二叉树的线索化Bit pre;/ 定义全局的指针变量，用于指向当前时刻的结点位置 /先序线索 void PreThreading(Bit p) / 先序线索化if(p) / 判断结点是否为空 if(!p->lchild)p->ltag=1;p->lchild=pre;/ 前驱线索if(!pre->rchild)pre->rtag=1;pre->rchild=p;/ 后继线索pre=p;/保持pre指向p的前驱if(p->ltag=0)PreThreading(p-&g

28、t;lchild);/ 左子树线索化 if(p->rtag=0)PreThreading(p->rchild); /右子树线索化Bit PreOrderThreading(Bit Thrt,Bit T) 先序遍历二叉树 T,并将其线索化，Thrt 指 向头结点并返回到主函数中Thrt=(Bit)malloc(sizeof(bit);/ 相内存中申请结点Thrt->data='#'/头指针内容为空Thrt->ltag=0;Thrt->rtag=1; /建立头结点 Thrt->rchild=Thrt;/ 右指针回指 if(!T)/ 若二叉树为空，

29、则左指针回指Thrt->lchild=Thrt;else Thrt->lchild=T;pre=Thrt;PreThreading(T);/先序遍历进行先序线索化pre->rchild=Thrt;pre->rtag=1;/ 最后一个结点的线索化 Thrt->rchild=NULL;return Thrt;void PreOrderThread(Bit T) /先序遍历if(T)/ 判断输出的内容if(T->ltag=0 && T->rtag=0)printf("%c 的 左 、 右 孩 子 分 别 为 ： %c %cn&quo

30、t;,T->data,T->lchild->data,T->rchild->data);if(T->ltag=1 && T->rtag=0)printf("%c 的 右 孩 子 和 前 驱 分 别 为：c %cn",T->data,T->rchild->data,T->lchild->data);if(T->ltag=0 && T->rtag=1)printf("%c 的 左 孩 子 和 后 继 分 别为： %c %cn",T->da

31、ta,T->lchild->data,T->rchild->data);if(T->ltag=1 && T->rtag=1)printf("%c 的 前 驱 和 后 继 分 别 为 ： %c %cn",T->data,T->lchild->data,T->rchild->data);if(T->ltag=0)PreOrderThread(T->lchild);/遍历左孩子if(T->rtag=0)PreOrderThread(T->rchild); / 遍历右孩子 /中

32、序线索 int InThreading(Bit p)/ 中序线索化if(p)InThreading(p->lchild);/ 左子树线索化 if(!p->lchild)p->ltag=1;p->lchild=pre;/ 判断结点的左孩子是否存在，让 其指向其前驱if(!pre->rchild)pre->rtag=1;pre->rchild=p;/ 后继线索化pre=p;保持pre指向p的前驱In Threadi ng(p->rchild); 右子树线索化 Bit InOrderThreading(Bit Thrt,Bit T)/ 中序遍历二叉树

33、T,并将其线索化，Thrt 指 向头结点并返回到主函数中Thrt=(Bit)malloc(sizeof(bit);/ 向内存中申请一个头结点Thrt->data=#;给头结点赋值为空Thrt->ltag=0;Thrt->rtag=1;Thrt->rchild=Thrt;/ 头结点右指针回指 if(!T)Thrt->lchild=Thrt;/ 若二叉树为空，则左指针回指 elseThrt->lchild=T;/二叉树不为空，左指针指向树 pre=Thrt;/pre 赋初值In Threadi ng(T);中序线索化二叉树pre->rchild=Thrt;

34、/最后一个结点线索化pre->rtag=1;Thrt->rchild=NULL;return Thrt; void InOrderThread(Bit T)if(T) if(T->ltag=0)PreOrderThread(T->lchild); /遍历左孩子 if(T->ltag=0 && T->rtag=0)printf("%c 的 左 、 右 孩 子 分 别 为 ： %c %cn",T->data,T->lchild->data,T->rchild->data);if(T->lta

35、g=1 && T->rtag=0)printf("%c 的 右 孩 子 和 前 驱 分 别 为：c %cn",T->data,T->rchild->data,T->lchild->data);if(T->ltag=0 && T->rtag=1)printf("%c 的 左 孩 子 和 后 继 分 别 为： %c %cn",T->data,T->lchild->data,T->rchild->data);if(T->ltag=1 &&

36、amp; T->rtag=1)printf("%c 的 前 驱 和 后 继 分 别 为 ： %c %cn",T->data,T->lchild->data,T->rchild->data);if(T->rtag=0)PreOrderThread(T->rchild); / 遍历右孩子 /后序线索 int PostThreading(Bit p)if(p)InThreading(p->lchild); InThreading(p->rchild); if(!p->lchild)p->ltag=1;p-&g

37、t;lchild=pre; if(!pre->rchild)pre->rtag=1;pre->rchild=p; pre=p; Bit PostOrderThreading(Bit Thrt,Bit T)Thrt=(Bit)malloc(sizeof(bit);Thrt->data='#'Thrt->ltag=0;Thrt->rtag=1;Thrt->rchild=Thrt; if(!T)Thrt->lchild=Thrt;elseThrt->lchild=T; pre=Thrt; InThreading(T); pre-&

38、gt;rchild=Thrt; pre->rtag=1; Thrt->rchild=NULL;return Thrt;void PostOrderThread(Bit T)为if(T)if(T->ltag=O)PreOrderThread(T->lchild); /遍历左孩子 if(T->rtag=O)PreOrderThread(T->rchild); / 遍历右孩子 if(T->ltag=O && T->rtag=O)printf("%c 的 左 、 右 孩 子 分 别 ：%c %cn",T->dat

39、a,T->lchild->data,T->rchild->data);if(T->ltag=1 && T->rtag=O)printf("%c 的 右 孩 子 和 前 驱 分 别为：%c %cn",T->data,T->rchild->data,T->lchild->data);if(T->ltag=O && T->rtag=1)printf("%c 的 左 孩 子 和 后 继 分 别为：为%c %cn",T->data,T->lch

40、ild->data,T->rchild->data);if(T->ltag=1 && T->rtag=1)printf("%c 的 前 驱 和 后 继 分 别 ：%c %cn",T->data,T->lchild->data,T->rchild->data);/将线索树还原成普通树int ReturnTree(Bit T)if(T->ltag=0)ReturnTree(T->lchild);/ 遍历左子树 ,找到 ltag=1 的结点 else T->lchild=NULL; /令

41、左指针指向空if(T->rtag=O)ReturnTree(T->rchild);遍历右子树，找到 rtag=1 的结点 else T->rchild=NULL;/令右指针指向空int CleanTree(Bit T)/树的清空if(T)if(T->lchild)CleanTree(T->lchild); if(T->rchild)CleanTree(T->rchild);free(T);void main()bit *L,*thrt; char x; printf(" printf(" printf("*n")

42、;二叉树的三种遍历（ #表示为空！）例如输入： abc#de#g#f#n");n");printf("*n");printf("L=CreateBiTree(L); while(1)请输入二叉树： ");=* 操 作 选 择* 遍 历* 请输入 *1n");* 线 索* 请输入 *2n");* 退 出* 请输入 *0n");操作数： ");printf("*=n");printf("printf("printf("printf(" sc

43、anf("%s",&x); switch(x)case '1':printf("先序遍历：");PreOrderTraverse(L);printf("n");printf(" 中序遍历： ");InOrderTraverse(L);printf("n"); printf(" 后序遍历： ");PostOrderTraverse(L);printf("n"); printf(" 广义遍历： ");GuangYi(

44、L);printf("n");break;case '2':thrt=PreOrderThreading(thrt,L);if(thrt)printf(" 二叉树先序线索化成功！ n");PreOrderThread(L);ReturnTree(L);free(thrt); thrt=InOrderThreading(thrt,L); if(thrt)printf(" 二叉树中序线索化成功！ n");InOrderThread(L);ReturnTree(L);free(thrt);thrt=PostOrderThre

45、ading(thrt,L);if(thrt)printf(" 二叉树后序线索化成功！ n");PostOrderThread(L);ReturnTree(L);free(thrt);break;case '0':break;default:printf(" 输入有误！请重新输入！ n");if(x='0')break;2、赫夫曼编码：#include<stdio.h> typedef struct / 赫夫曼编码结构体char ch;/编码存储类型un sig ned int weight;/权值unsigne

46、d int parent,lchild,rchild; / 双亲、左孩子、右孩子 HTNode,*HuffmanTree;typedef char *HuffmanCode;/动态分配数组存储赫夫曼编码int Select(HuffmanTree HT,int n,int *s1,int *s2) /在赫夫曼树中选取两个双亲为 零且权值最小的两个节点，用s1、s2 返回int i,j;for(j=1;j<=n;+j)if(HTj.parent=0)/选取第一个双亲不为零的结点赋值给s1*s1=j;break;for(i=j+1;i<=n;+i) if(HTi.weight<H

47、T*s1.weight&&HTi.parent=0)/ 选出权值最小的节 点八、*s1=i;for(j=1;j<=n;+j)/选出双亲为零且不是si的结点if(HTj.parent=0&&*s1!=j)*s2=j;break;for(i=j+1;i<=n;+i) if(HTi.weight<HT*s2.weight&&HTi.parent=0&&*s1!=i) /选出权值 次小的节点s2=i;if(*s2<*s1) /判断两个权值的大小是否符合要求，不符合交换i=*s1;*s1=*s2;*s2=i;void

48、 HuffmanCoding(HuffmanTree HT,HuffmanCode *HC,int n) /构造赫夫曼树 HT,并求出赫夫曼树所对应的的赫夫曼编码int i,j,f,m,c,start;int S1,S2;char *cd;m=n*2;for(i=1;i<=n;i+)/初始构造赫夫曼树printf("请输入第%d个字符和字符对应权值(中间用空格隔开，女口： g 29):",i);scanf("%s %d",&HTi.ch,&HTi.weight);HTi.parent=0; /双亲和左右孩子均初始化为 0；HTi.l

49、child=0;HTi.rchild=0;for(;i<m;i+) /将没有存放字符的结点权值、双亲和左右孩子均初始化为0HTi.weight=0;HTi.lchild=0;HTi.rchild=0;HTi.parent=0;for(i=n+1;i<m;i+)Select(HT,i-1,&S1,&S2);/从结点中选取两个最小的结点HTS1.parent=i;HTS2.parent=i; /将新结点的位置的值赋给最小的两 个结点的双亲HTi.lchild=S1;HTi.rchild=S2; /将最小的两个结点的位置的值赋给 新结点的左右孩子HTi.weight=HTS1.weight+HTS2.weight; /将两个最小结点的权值 相加赋新结点的权值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)/ 从叶子到根逆向求编码 if(