13、二叉树应用实验

《13、二叉树应用实验》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、实验十二二叉树应用实验一、实验目的1、掌握用VC工具上机调试二叉树的链式存储结构及其基本操作。2、掌握二叉树应用哈夫曼编码。。二、实验学时2学时三、实验类型验证型四、实验内容二叉树的链式存储结构与基本操作算法实现、哈夫曼树的构造与实现。五、实验原理1、哈夫曼树概述从二叉树的一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称为路径长度，二叉树的路径长度是从树根到每一个结点的路径长度之和。假设有n个权值，构造一颗有n个叶子结点的二叉树，每个叶子结点赋权，则其中带权路径长度最小的二叉树称为最优二叉树或哈夫曼

2、树。哈夫曼编码是哈夫曼树德一个应用。在远距离通信中要对字符进行编码，可以根据字符出现的次数设计对每个字符编码的长度，并且任一个字符的编码都不是另一个字符编码的前缀（这种编码称前缀编码），这样可使电文尽可能短且有唯一的译码，使用哈夫曼编码可使字符编码称为最简编码。2、哈夫曼树及编码的基本算法(1)Select(HuffmanTreep,unsignedi,int*s1,int*s2)；选择parent为0，且weight最小的两个结点。(2)Huffman()；构造哈夫曼树及哈夫曼编码。3、模块层次图要求画出二叉树的程序模块层

3、次图。如图所示图19哈夫曼编码程序模块层次图4、关键算法NS图六、实验步骤及要求用VC语言编程实现哈夫曼树的构造与编码算法。1.输入要编码的字符个数n；2.依次输入每个字符对应的权值；1.构造哈夫曼树T；2.对每个字符编码；3.输出每个字符对应的编码；4.程序运行结束。七、运行结果图24哈夫曼树编码算法运行图八、思考问题结合实验过程，回答下列问题：1、如何构造哈夫曼树？试写出相应的算法。2、哈夫曼编码是否是最优编码？为什么？3、能否采用哈夫曼编码原理实现电文的编码与译码？九、实验报告要求1、根据对哈夫曼树的理解，如何编写哈夫

4、曼树的建立？哈夫曼编码及哈夫曼编码的输出？2、对一组预先指定的电文进行哈夫曼编码；3、调试程序过程中遇到的问题及解决方案；4、本次实验的结论与体会。程序附录：哈夫曼树的构造、编码及输出。#include#include#includetypedefstruct{intweight;intparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;voidSelect(HuffmanTreep,u

5、nsignedi,int*s1,int*s2){/*选择parent为0，且weight最小的两个结点*/unsignedj;for(j=1;jp[j].weight){*s2=*s1;*s1=j;}else*s2=j;}}if(*s1&&*s2)break;}for(j++;jp[j].weight){*s2=*s1;*

6、s1=j;}else{if(p[*s2].weight>p[j].weight)*s2=j;}}}}intHuff()/*构造哈夫曼树及哈夫曼编码*/{intn,m,i,s1,s2,start,c,f;char*cd;HuffmanTreeHT,p;HuffmanCodeHC;printf("请您输入要编码的字符个数:");scanf("%d",&n);if(n<2)return1;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));/*0号单元未用*/if(!HT)

7、return1;for(p=HT+1,i=1;i<=n;i++,p++){printf("请您输入第%d个字符权值：",i);scanf("%d",&p->weight);p->lchild=p->parent=p->rchild=0;}for(;i<=m;i++,p++)p->lchild=p->parent=p->rchild=p->weight=0;/*建赫夫曼树*/for(i=n+1;i<=m;i++){s1=s2=0;Select(HT,i,&s1,&s2);/*选择parent为0，且weight最小的两个结点*

8、/HT[s1].parent=HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}/*从叶子到根逆向求每个字符的哈夫曼编码*/HC=(HuffmanCode)ma