二叉树的实现

1、江西理工大学软件学院计算机类课程实验报告课程名称：数据结构班 级：姓 名:学 号：江西理工大学软件学院实验六实验名称二叉树的实现实验日期2012-12-21实验成绩实验目的掌握二叉树的逻辑结构掌握二叉树的带权路径长度实验目的加深二叉树的理解，逐步培养解决实际问题的编程能力实验目的二、实验要求程序要求实现以下功能：统计文本文件中各字符的出现次数(涉及读文件，统计字符个数);2对文件中的字符进行哈夫曼编码，并存储入字符编码文件；根据字符编码文件对文本文件内容进行编码；根据字符编码文件和已编码文件的内容进行译码；能够输出原文、编码表、文本文件编码、译文。3423机房操作系统：windows XPC

2、环境：VC+ 6.0一、哈夫曼树建立算法：1）根据给定的n个权值 W1, W2, W3Wn 构成n棵二叉树的集合T1, T2,Tn，其中Ti中只有一个权值为Wi的根结点，左右子树均为空。2）在F中选取两棵根结点的权值最小的树作为左、右子树一构造一棵新的二 叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。3）在F中删除这两棵中权值最小的树，同时将新得到的二叉树加入F中。4）重复2） 3）直到F中仅剩一棵树为止，这棵树就是哈夫曼树。2、哈夫曼编码算法：通过从哈夫曼树根结点开始，对左子树分配代码“ 1”，右子树分配代码“0”， 一直到达叶子结点为止，然后将从树根沿每条路径到达叶子结

3、点的代码排列起来, 便得到了哈夫曼编码。3、对文件字符编码算法：逐一读取文件中字符，在哈夫曼编码表查找对应字符，读取其编码并写入文件, 如此循环直至结束。算法描述及实验步骤4、哈夫曼译码算法：算法描述及实验步骤根据编码用的哈夫曼树，从根结点出发，逐个读入电文中的二进制码；若代码 为“1”，则走左子树的根结点，否则走向右子树的根结点；一旦到达叶子结点， 便译出代码所对应的字符。然后又重新从根结点开始继续译码，直到二进制电文结 束。二、实验步骤1、输入电文：yangyang2、电文长度：83、权值：24、电文哈夫曼的编码：00011011000110114,上机调试，验证。调试过程及实验结果实验结

4、果:调试过程及实验结果c： E:HuffmanTreeDebugHuffmanTree.exe数据结构课程设计接受到的电文内容不超过50个字符）t yangyang电文的长度対h.8叶子结点权值y2a2n2g2叶子结点权值左孩子父母结点花孩子y (004S2E50)200000000 #00492EBO00000000 #a (00492E68)200000000 I00492EB000000000 #n (00492E3QT200000000 #00492EC300000000 #g (OO492E9eS-2OOWWjO #00492EC8b wooojo #?(004$2EBG)4004S

5、2E50 y004&2EEO004&68 a?(00492EC8)400492ESO； n00492EE0；00492E9&. g?(00492EE0j800492EB000000000 00492EC8?(00492EE0)8O0492EB0叶子结点编码y?(00492EE0)8O0492EB0叶子结点编码y00a01n10g1100492EC8电文内容：yangyang电文的赫夫曼编码:000110110011011 程序结束Press any key to continue执行正确总结通过本次数据结构的实验，我理解很多之前上课没懂的知识，对求二叉树及二 哈夫曼编码/译码的算法有了更加深刻

6、的了解，更巩固了课堂中学习有关于哈夫曼 编码的知识，真正学会一种算法了。当求解一个算法时，不是拿到问题就不加思索 地做，而是首先要先对它有个大概的了解，接着再详细地分析每一步怎么做，无论 自己以前是否有处理过相似的问题，只要按照以上的步骤，必定会顺利地做出来。本次实验虽然实现了哈夫曼编码/译码等要求，但由于时间等各方面原因，仍 有一些问题没有解决，例如一些要求输入判断时判断不严格、操作界面不够美观等， 总体上还有待改进。(源程序清单等)把构造赫夫曼树的函数放在头文件构造赫夫曼树.h中#includeviostream#include 计算权值.husing namespace std;type

7、def struct nodel/赫夫曼树的结点结构体 _char a;/结点元素int weight,sign;结点的权值和结点的标记struct nodel *parent,*lchild,*rchild;指向父母结点和左、右孩子的指针*listnode1;指向 node1 的指针 构造赫夫曼树的函数listnode1 settree(listnode head)listnode p;listnode1 p0,p1,p2;int m,n,i,j,k1,k2;struct node1 *p3,*p4;统计叶子结点个数n=0;for(p=head-next;p!=NULL;p=p-next)

8、n+;动态存储分配开辟可以存储2n个赫夫曼树结点的顺序表 p0=(listnode1)malloc(2*n*sizeof(node1); /HuffmanTree结点初始化/把叶子结点的信p1=p0；/把叶子结点的信息读入到顺序表中 p1-a=p-a; / 字符信息 p1-weight=p-b; 权值 p1-lchild=NULL;左右孩子及双亲结点均置空 p1-parent=NULL;p1-rchild=NULL; p1-sign=NULL;结点标志置空 p1+；循环结束后p0指向HuffmanTree顺序表的头p1指向HuffmanTree顺序表的尾下面的循环进行n-1次合并，生成新的Hu

9、ffmanTree的非叶子结点for(i=1;i=n-1;i+)for(j=0;jsign=NULL) m=p2-weight; break;找到权值的最小值，赋给mfor(p2=p0;p2!=p1;p2+) if(m=p2-weight)if(p2-sign=NULL) m=p2-weight;for(p2=p0;p2!=p1;p2+)if(m=p2-weight)/p2所指结点的权值最小 if(p2-sign=NULL)p2-sign=1;修改结点标志为1 把先找到的权值最小的作为左孩子 if(j=0) p1-lchild=p2; p1-weight=p2-weight; p2-paren

10、t=p1;把后找到的权值最小的最为右孩子else if(j=1) p1-rchild=p2; p1-weight=p1-weight+p2-weight; p2-parent=p1;break;标记先找到的权值最小的结点在顺序表中的位置 if(j=0)k1+;标记后找到的权值最小的结点在顺序表中的位置 else if(j=1)k2+; if(k1k2)/*如果先找到的权值最小的结点在顺序表中的位置在后找到的后面 则他们父母结点的左右孩子指针交换*/p3=p1-lchild;p4=p1-rchild;p1-lchild=p4;p1-rchild=p3;pl-sign=NULL;pl+；p1-;p

11、1-parent=NULL;对于生成的最后一个结点的双亲结点置空p1+；输出构造的赫夫曼树p2=p0;coutvv叶子结点vvttvv权值vvtvv左孩子vvttvv父母结点vvtvv右孩子vvendl;while(p2!=p1)。0皿8(卩2weightvvt;coutlchildlchild!=NULL) coutlchild-a;else coutvv#;。0皿尸卩82皿parent!=NULL) coutvvp2-parent-a;else coutvv; coutvvtvvp2-rchildvv; if(p2-rchild!=NULL) coutvvp2-rchild-a;else

12、coutvv#;coutvvendl;vvendl;p2+;vvendl;coutvv -return p0;把叶子结点赫夫曼编码的获取的函数放在头文件获得赫夫曼编码.h中#includeviostream存储赫夫曼编码的结构体/存储O、T编码#include 存储赫夫曼编码的结构体/存储O、T编码struct code *next;*listcode;typedef struct huffmancode 指针的结构体char a; listcode head; *listhuffmancode;listcode setcode()开辟存储0、1编码结点的函数listcode p; p=(li

13、stcode)malloc(sizeof(code); return p;listhuffmancode gethuffmancode(listnode1 p) / 把得到的叶子结点及其/ 赫夫曼编码存到顺序表中的函数listnode1 p1,p2,p4;int n=0;listhuffmancode l,l1;listcode h,h1; for(p2=p;p2-lchild=NULL&p2-rchild=NULL;p2+) n+;l=(listhuffmancode)malloc(n+l)*sizeof(huffmancode);/ 开辟可以存储 n+1 个叶子结点信息的顺序表l1=l;

14、for(p4=p;p4-lchild=NULL&p4-rchild=NULL;p4+)p1=p4;h1=setcode();l1-head=h1; for(;p1-parent!=NULL;p1=p1-parent)if(p1=p1-parent-lchild)h=setcode();h-a=0;h1-next=h;h1=h;else if(p1=p1-parent-rchild)h=setcode();h-a=1;h1-next=h;h1=h;h1-next=NULL;l1-a=p4-a;l1+;l1-a=NULL;return l;/存储叶子结点元素及其权值的结构体/叶子结点的元素/叶子结

15、点的权值/存储叶子结点元素及其权值的结构体/叶子结点的元素/叶子结点的权值/指向下一个结点的指针/开辟结点的函数int b;struct node *next; *listnode;listnode setnode()listnode p;p=(listnode)malloc(sizeof(node);return p;listnode getdata(char *a)/*统计输入字符串中的不同字符及其出现的次数的函并且把统计出的数据，作为叶子结点的元素和权值*/listnode head,p1,p2;char *n,*t,*h;int i=1,j=1,r=0;head=setnode();p

16、1=head;for(n=a;*n!=0;n+)if(n=a)p2=setnode();/统计第一个字符在字符串中出现的次数 for(t=n;*t!=0;t+)if(*t=*n)r+;p2-a=*n;p2-b=r;p1-next=p2;p1=p2;elsei+;r=0;j=1; /统计相同的字符在字符串中出现的次数 for(t=a;*t!=0;t+)if(*t=*n) r+;/统计当前字符是第几个字符与前面不相同的字符 for(h=a;h!=n;h+)if(*h=*n) break;elsej+;if(i=j)/?p2=setnode();/调用 setnode ()函数开辟结点八、p2-a=

17、*n;p2-b=r;p1-next=p2;p1=p2;p1-next=NULL;coutvv电文的长度为：vvivvendl;coutnext;p1!=NULL;p1=p1-next)coutvvp1-avvtt vvp1-bvvendl;coutvvvvendl;return head;/统计叶子结点的个数/统计叶子结点的个数int coutdata(listnode head)listnode p;int n=0;for(p=head-next;p!=NULL;p=p-next)n+;return n;把control函数放在头文件”控制函数.h”中#includeviostream#in

18、clude输出赫夫曼编码.h using namespace std;void control()/调用各个功能函数coutvv数据结构课程设计vvendl;coutvvvvendl;char a50;int n;coutvv接受到的电文内容(不超过50个字符)：；cina;listnode p;p=getdata(a);n=coutdata(p);if(n=1)/如果只有一个叶子结点，说明该叶子结点就是根结点，无法构造赫夫曼树p=p-next;coutvv该树只有一个叶子结点即根结点(根结点没有赫夫曼编码)vvendl;coutvv根结点vvttvv权值vvendl;coutvvp-avvt

19、t vvp-bvvendl;coutvvvvendl;elselistnode1 p1;p1=settree(p); /构造赫夫曼树listhuffmancode p2;p2=gethuffmancode(p1); /获得 Huffman 编码printhuffmancode(p2); /打印 Huffman 编码print(a,p2);coutvvendlvv程序结束vvendl;#includeviostream#include获得赫夫曼编码.husing namespace std;void printhuffmancode(listhuffmancode head1)/输出叶子结点及其赫夫曼编码的函数listhuffmancode p;p=head1;listcode h;int n;char *base,*top;coutvv叶子结点vvtvv 编码vvendl;for(p=head1;p-a!=NULL;p+)coutvvp-avvtt ;n=0;h=p-head;for(h=h-next;h!=NULL;h=h-next)n+;base=(char *)malloc(n+1)*sizeof(char);t