（规格为A4纸或A3纸折叠）（用五号宋体和TimesNewRoman,A4纸双面打印）实验目的；通过本实验，熟悉二叉树、Huffman树的基本概念，掌握二叉树的存储结构与各种算法。熟悉用Huffman树进行电文的加密与解密算法。实验内容；Huffman树的存储方式。加密与解密算法在电文编码中的应用。三、实验原理；给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，又称为哈夫曼树（Huffmantree）。Huffman树是一种特殊的二叉树，其叶结点的编码是一种前缀码，同时，通过统计字符的频度，能够达到编码电文的最小化。假设有n个权值，则构造出的哈夫曼树有n个叶子结点。n个权值分别设为w1、w2、…、wn，则哈夫曼树的构造规则为：将w1、w2、…，wn看成是有n棵树的森林（每棵树仅有一个结点）；在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；从森林中删除选取的两棵树，并将新树加入森林；重复（2）、（3）步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。四、实验步骤；1.调试下列程序“二叉树程序一”，掌握链式二叉树构造的算法和实现方式。2.根据二叉树程序的学习，完成Huffman树的构造、编码和解码的实现。（1）统计电文中字符的出现频率。（2）用统计频率建立Huffman树，并生成前缀码；（3）建立Huffman树的解码算法。（4）用随机输入的电文完成编码与解码过程。五、程序源代码及注释#include<stdio.h>#include<malloc.h>#include<string.h>typedefstruct{charch;intweight;intparent,lchild,rchild;}HTnode,*Huffmantree;//动态分配数组存储赫夫曼树typedefchar**Huffmancode;//动态分配数组存储赫夫曼编码表intmain(){//------------构造赫夫曼树及赫夫曼编码-------------------HuffmantreeHT;HuffmancodeHC;char*cd,s[100],g[100];intn,mm,m,i,j=0,f,start,c,s1=0,s2=0,temp1,temp2;intw[26];inta[26]={0};printf("请输入字符：");gets(s);n=strlen(s);HT=(Huffmantree)malloc((m+1)*sizeof(HTnode));//0号单元未用for(i=0;i<n;i++)a[s[i]-'a']++;for(i=0;i<26;i++)if(a[i]!=0){w[j]=a[i];j++;}n=j;m=2*j-1;HT=(Huffmantree)malloc((m+1)*sizeof(HTnode));for(i=0,j=0;i<26;i++)if(a[i]!=0){HT[j+1].ch=i+'a';j++;}for(i=1,j=0;i<=n;++i,++j){HT[i].weight=w[j];HT[i].parent=HT[i].lchild=HT[i].rchild=0;}for(;i<=m;++i)HT[i].weight=HT[i].parent=HT[i].lchild=HT[i].rchild=0;//除叶子外的节点赋初值for(i=n+1;i<=m;i++){//建赫夫曼树//在HT[1..i-1]选择parent为0且weight最小的两个节点，其序号为别为s1,s2.temp1=temp2=100;for(j=1;j<=i-1;j++)if(HT[j].parent==0)if(HT[j].weight<temp1){temp1=HT[j].weight;s1=j;}for(j=1;j<=i-1;j++)if(HT[j].parent==0&&j!=s1)if(HT[j].weight<temp2){temp2=HT[j].weight;s2=j;}HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;//父节点权值为左右两孩子权值之和}printf("numweightlchildparentrchildch\n");for(i=1;i<=m;i