数据构造试验汇报试验名称：试验三树学生姓名：班级：班内序号：学号：日期：12月7号1、试验规定运用二叉树构造实现赫夫曼编/解码器。基本规定：1、初始化(Init)：可以对输入的任意长度的字符串s进行记录，记录每个字符的频度，并建立赫夫曼树2、建立编码表(CreateTable)：运用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。4、译码(Decoding)：运用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码成果。5、打印(Print)：以直观的方式打印赫夫曼树（选作）6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。测试数据：IlovedataStructure,IloveComputer。IwilltrymybesttostudydataStructure.提醒：1、顾客界面可以设计为“菜单”方式：可以进行交互。2、根据输入的字符串中每个字符出现的次数记录频度，对没有出现的字符一律不用编码。2、程序分析2.1存储构造（1）二叉树templateclassBiTree{public:BiTree();//构造函数，其前序序列由键盘输入~BiTree(void);//析构函数BiNode*Getroot();//获得指向根结点的指针protected:BiNode*root;//指向根结点的头指针};//申明类BiTree及定义构造BiNodeData：二叉树是由一种根结点和两棵互不相交的左右子树构成。二叉树中的结点具有相似数据类型及层次关系。示意图：rootlchildparentrchild（2）静态三叉链表structHNode//哈夫曼树的静态三叉链表{unsignedintweight;//结点权值unsignedintparent;//双亲指针unsignedintLchild;//左孩子指针unsignedintRchild;//右孩子指针};示意图：(3)编码表的节点构造structHCode//字符及其编码构造{chardata;charcode[100];};示意图：2.2关键算法分析一：关键算法(一)初始化函数voidHuffman::Init(inta[],intn)（1）算法自然语言1.创立一种长度为2*n-1的三叉链表2.将存储字符及其权值的链表中的字符逐一写入三叉链表的前n个结点的data域，并将对应结点的孩子域和双亲域赋为空3.从三叉链表的第n个结点开始，i=ndataLchildRchildparentchardatacharcode[100]3.1从存储字符及其权值的链表中取出两个权值最小的结点x,y，记录其下标x,y。3.2将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点3.3将下标为x的结点设置为i结点的左孩子，将下标为y的结点设置为i结点的右孩子，i结点的权值为x结点的权值加上y结点的权值，i结点的双亲设置为空4.根据哈夫曼树创立编码表（2）源代码voidHuffman::Init(inta[],intn)//创立哈夫曼树{//二叉树只有度为和度为的结点时，总结点数为（n-1）个HTree=newHNode[2*n-1];//根据权重数组a[1—>n]初始化哈夫曼树inti,x,y;for(i=0;i
