树的应用哈夫曼编码

1、数据结构实验报告20142015学年 第学期 2012级 计算机科学与技术专业班级： 学号： 姓名：实验三树的应用实验题目:树的应用哈夫曼编码实验内容:第 3 页 共 9 页1 .编写程序，完成以下功能:(1)建立二叉树(2)输出二叉树(3)输出二叉树(4)输出二叉树(5)输出二叉树(6)输出二叉树B；B；B的深度；B的宽度；B的节点个数；B的叶子节点个数2 .编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，求 出各字符的哈夫曼编码。要求：(1)输出存放哈夫曼树的数组 HT的初态和终态；(2)输出每个字

2、符的哈夫曼编码；(3)输入由上述若干字符组成的字符串，对电文进行编码并输出；(4)(选作)输入电文的哈夫曼编码，进行译码并输出。三、程序设计过程及源代码：(一)设计思路：首先初始化一个二叉树链，其中建立一个栈用来建立之前根节点和其他孩子节点的关系。主要思路就是将根节点与其左右节点进栈，然后依次退栈，知道最后栈为空，二叉树构建完成。求高度、 宽度和二叉树输出，以及求节点数、叶子节点数的时候都用到了递归算法，特别强调的是不仅要逐层递加(扫描每一层)，还要扫描每一层上的节点数，用数组 ni表示每一层节点。源代码：#include#include#define MaxSize 30typedef st

3、ruct nodeint data;struct node *lchild;struct node *rchild;BTnode;void CreateBTnode(BTnode *&b,char *str) BTnode *stMaxSize,*p;int top=-1,k,j=0;char ch;b=NULL;ch=strj;while(ch!=0) switch(ch)case(:top+;sttop=p;k=1;break;case):top-;break;case,:k=2;break;default:p=(BTnode*)malloc(sizeof(BTnode); p-data=

4、ch;p-lchild=p-rchild=NULL; if(b=NULL)b=p;else switch(k) case 1:sttop-lchild=p;break;case 2:sttop-rchild=p;break; j+;ch=strj;void DispBTnode(BTnode *b)if(b!=NULL)printf(%c,b-data);if(b-lchild!=NULL|b-rchild!=NULL)printf();DispBTnode(b-lchild);if(b-rchild!=NULL) printf(,);DispBTnode(b-rchild);printf()

5、;int BTnodeHeight(BTnode *b)/ 高度int lchildh,rchildh,h;if(b=NULL) return 0;elselchildh=BTnodeHeight(b-lchild);rchildh=BTnodeHeight(b-rchild);h=(lchildhrchildh)?(lchildh+1):(rchildh+1);return h;int LeafNodes(BTnode *b)/ 叶子结点的个数 int num1,num2,n;if(b=NULL) n=0;elseif(b-lchild=NULL & b-rchild=NULL) n=1;e

6、lsenum1=LeafNodes(b-lchild);num2=LeafNodes(b-rchild);n=num1+num2;return n;int Nodes(BTnode *b)/ 结点个数int n;if (b=NULL) n=0;elsen=Nodes(b-lchild)+Nodes(b-rchild)+1; return n;void BTWidth(BTnode *b,int i,int n,int &max)if(b!=NULL)n+i+;/+i 表示逐层递增，在每一层上的扫描每个叶子节点if(nimax) max=ni;/max 表示最大宽度if(b-lchild!=NU

7、LL)BTWidth(b-lchild,i,n,max);if(b-rchild!=NULL)BTWidth(b-rchild,i,n,max);void main()BTnode *b;char *str=a(b(,e(j,k),c(f,g);int a,lf,c;int i=0,n15=0,max=0;CreateBTnode(b,str);printf(输出二叉树为：)；DispBTnode(b);printf(n);a=BTnodeHeight(b);printf(二叉树的高度为：dn,a);lf=LeafNodes(b);printf(二叉树的叶子节点个数为 ：dn,lf);c=No

8、des(b);printf(二叉树的节点个数为：dn,c);BTWidth(b,i,n,max);printf(二叉树的宽度为：dn,max);测试结果：T为ti e数:8on n c 见y J的的 an -J二：JJ _ N.仪w s 田叉叉叉叉es 电Ejl三昨（二）哈夫曼实验设计思路：首先构造哈夫曼树和哈夫曼编码，在主函数里定义两个数组ht口和hcd,分别用来存放哈夫曼树节点和哈夫曼编码，由于每个哈夫曼编码可能不一样长度，所以用start指向每个哈夫曼编码的首位置，cdstartcdn表示存放其中的各个哈夫曼编码。输出初态之前要先将字符和权值初始化，然后输出初态和终态，最后用 ch口数组

9、承接，输出由以上字符构成的字符串，终态用for循环输出，hcdi.cdj即每个编号为i的哈夫曼编码。源代码如下： #include #include #define N 10哈夫曼编码的个数#define M 5 typedef struct char data;/ 节点值 double weight;/ 权重 int parent; int lchild; int rchild; HTNode;/哈夫曼树节点typedef struct char cdN;/ 存放当前节点的哈夫曼编码int start;/cdstartcdn(每个哈夫曼码都是从startn)HCode;/ 哈夫曼编码节点vo

10、id CreateHT(HTNode ht,int n)/ 构造哈夫曼树 int i,k,lnode,rnode;double min1,min2;for(i=0;i2*n-1;i+)/ 所有节点的相关域置初值-1hti.parent=hti.lchild=hti.rchild=-1;for(i=n;i2*n-1;i+) min1=min2=32767;/lnode 和 rnode 为权值最小的两个节点位置lnode=rnode=-1;for(k=0;k=i-1;k+)/ 在 ht 中找权值最小的两个节点位置if (htk.parent=-1)/ 在还没构造二叉树的节点中查找 if (htk.

11、weightmin1) min2=min1;rnode=lnode;min1=htk.weight;lnode=k; else if(htk.weightmin2)min2=htk.weight; rnode=k; hti.weight=htlnode.weight+htrnode.weight;hti.lchild=lnode;hti.rchild=rnode;/hti作为双亲节点htlnode.parent=htrnode.parent=i;void CreateHCode(HTNode ht,HCode hcd,int n)/哈夫曼编码int i,f,c;HCode hc;for(i=0

12、;in;i+) hc.start=n;c=i;f=hti.parent;while(f!=-1) if( htf.lchild=c) hc.cdhc.start-=0;elsehc.cdhc.start-=1; c=f;f=htf.parent; hc.start+; hcdi=hc; void main() HTNode ht2*M-1;定义一个有 T个节点的哈夫曼数组HCode hcdM;/定义一个含有 M个元素的哈夫曼编码数组 char chN;int i,j,t;for(i=0;i2*M-1;i+)/ 初始化 hti.data=NULL; hti.weight=0; printf( 输

13、入字符、权值以及输出存放哈夫曼树的数组的初态和终态n);printf( 输入 外字符：n”,M); for(i=0;iM;i+) scanf(%c,&hti.data); printf( 输入各字符的权值: n);for(i=0;iM;i+) scanf(%lf,&hti.weight); CreateHT(ht,M); printf( 哈夫曼树初态为：n 节点编号字符 权值 n);for(i=0;iM;i+) printf(第 djtt%ct%2.2fn”,i,hti.data,hti.weight); printf( 哈夫曼树终态为：n 节点编号t 字符 t 权值 t 左孩子 t 右孩子

14、t 双亲 n);for(i=0;i2*M-1;i+)printf(第%d个tt%ct%2.2ft%dt%dt%dn,i,hti.data,hti.weight,hti.lchild,hti.rchild,hti.pare nt); for(i=0;iM;i+)for(int j=0;jN;j+) hcdi.cdj=NULL;CreateHCode(ht,hcd,M);for(i=0;iM;i+)第 6 页 共 9 页printf(%c的哈夫曼编码是：,hti.data);for(j=hcdi.start;j=M;j+)printf(%c,hcdi.cdj);printf(n);printf( 输入由以上字符组成的字符串，对电文编码并输出：n);printf(请