资源描述：
《树的应用-哈夫曼编码》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构实验报告2014～2015学年第一学期2012级计算机科学与技术专业班级：学号：姓名：实验三树的应用一、实验题目：树的应用——哈夫曼编码二、实验内容：1.编写程序，完成以下功能：（1）建立二叉树B；（2）输出二叉树B；（3）输出二叉树B的深度；（4）输出二叉树B的宽度；（5）输出二叉树B的节点个数；（6）输出二叉树B的叶子节点个数2.编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，求出各字符的哈夫曼编码。要求：（1）输出存放哈夫曼树的数组HT的初态和终态；（2）输出每个字符的哈夫曼编码；（
2、3）输入由上述若干字符组成的字符串，对电文进行编码并输出；（4）（选作）输入电文的哈夫曼编码，进行译码并输出。三、程序设计过程及源代码：(一)设计思路：首先初始化一个二叉树链，其中建立一个栈用来建立之前根节点和其他孩子节点的关系。主要思路就是将根节点与其左右节点进栈，然后依次退栈，知道最后栈为空，二叉树构建完成。求高度、宽度和二叉树输出，以及求节点数、叶子节点数的时候都用到了递归算法，特别强调的是不仅要逐层递加（扫描每一层），还要扫描每一层上的节点数，用数组n[i]表示每一层节点。源代码：#include#include#defineMaxSize3
3、0typedefstructnode{intdata;structnode*lchild;structnode*rchild;}BTnode;voidCreateBTnode(BTnode*&b,char*str){BTnode*st[MaxSize],*p;第8页共8页inttop=-1,k,j=0;charch;b=NULL;ch=str[j];while(ch!=' '){switch(ch){case'(':top++;st[top]=p;k=1;break;case')':top--;break;case',':k=2;break;default:p=(BTnode*)mal
4、loc(sizeof(BTnode));p->data=ch;p->lchild=p->rchild=NULL;if(b==NULL)b=p;else{switch(k){case1:st[top]->lchild=p;break;case2:st[top]->rchild=p;break;}}}j++;ch=str[j];}}voidDispBTnode(BTnode*b){if(b!=NULL){printf("%c",b->data);if(b->lchild!=NULL
5、
6、b->rchild!=NULL){printf("(");DispBTnode(b->lchild);if(
7、b->rchild!=NULL)printf(",");DispBTnode(b->rchild);printf(")");}}}intBTnodeHeight(BTnode*b)//高度{intlchildh,rchildh,h;if(b==NULL)return0;else{第8页共8页lchildh=BTnodeHeight(b->lchild);rchildh=BTnodeHeight(b->rchild);h=(lchildh>rchildh)?(lchildh+1):(rchildh+1);returnh;}}intLeafNodes(BTnode*b)//叶子结点的个数{i
8、ntnum1,num2,n;if(b==NULL)n=0;else{if(b->lchild==NULL&&b->rchild==NULL)n=1;else{num1=LeafNodes(b->lchild);num2=LeafNodes(b->rchild);n=num1+num2;}}returnn;}intNodes(BTnode*b)//结点个数{intn;if(b==NULL)n=0;elsen=Nodes(b->lchild)+Nodes(b->rchild)+1;returnn;}voidBTWidth(BTnode*b,inti,intn[],int&max){if(b!
9、=NULL){n[++i]++;//++i表示逐层递增，在每一层上的扫描每个叶子节点if(n[i]>max)max=n[i];//max表示最大宽度if(b->lchild!=NULL)BTWidth(b->lchild,i,n,max);if(b->rchild!=NULL)BTWidth(b->rchild,i,n,max);}}voidmain(){BTnode*b;第8页共8页char*str="a(b(,e(j,k)),c
