数据结构实验报告6-二叉树与哈夫曼树

数据结构与算法》实验指导V2016数据结构与算法》实验指导V2016常熟理工学院计算机科学与工程学院#实验六二叉树实验目的】1、掌握二叉树的基本存储表示。2、掌握二叉树的遍历操作实现方法(递归和非递归方法)3、理解并实现二叉树的其他基本操作。4、掌握二叉树的重要应用哈夫曼编码的实现。实验学时】4-6学时实验预习】回答以下问题：1、二叉树的二叉链表存储表示。typedefstructBiTNode{//结点结构ElemTypedata；//数据域structBiTNode*Lchild；//左孩子指针structBiTNode*Rchild；〃右孩子指针}BiTNode，*BiTree；voidCreate(BiTree&T){//输入扩展二叉树的先序序列，构建二叉链表scanf(&ch);//输入一个元素if(ch=='#')T=NULL;else{T=(BiTree)malloc(sizeof(BiTNode))；//申请根结点T->data=ch;//给根结点数据域赋值Create(T->Lchild);〃建左子树Create(T->Rchild);〃建右子树}}//Create2、二叉树的三种基本遍历方式。前序遍历(DLR),首先访问根结点，然后遍历左子树，最后遍历右子树。简记根-左-右。中序遍历(LDR)，首先遍历左子树，然后访问根结点，最后遍历右子树。简记左-根-右。后序遍历(LRD)，首先遍历左子树，然后遍历右子树，最后访问根结点。简记左-右-根。

3、解释哈夫曼树和带权路径长度WPL。哈夫曼树：它是最优二叉树。定义：给定n个权值作为n个叶子结点，构造一棵二叉树，若树的带权路径长度达到最小，则这棵树被称为哈夫曼树。路径和路径长度定义：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1。结点的权及带权路径长度定义：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。树的带权路径长度定义：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。实验内容和要求】1、编写程序exp6_l.c，实现二叉树的链式存储及基本操作。以下图所示的二叉树实现二叉树的二叉链表存储及基本操作，回答下列问题，补充完整程序，并调试运行验证结果。ABXACADAABXACADAEAFAAGA（1）按照先序序列建立该二叉树。读入的字符序列应为：ABCDEFG（*表示空指针）（2）该二叉树的三种遍历序列：TOC\o"1-5"\h\z先序序列：__ABCDEFG;中序序列：__CBEGDFA;后序序列：__CGEFDBA;（3）按层次遍历该二叉树，得到的序列为：ABCDEFG。（4）该二叉树的深度为：__4。（5）该二叉树的叶子结点数为：3。（6）交换该二叉树所有结点的左右次序得到的新二叉树为：（画出新二叉树的图）（7）新二叉树的三种遍历序列分别为：先序序列：ABDFEGC中序序列：AFDGEBC后序序列：FGEDCBAexp6_1.c参考程序如下：#include<stdio.h>#include<malloc.h>#defineMAX20/*二叉树的二叉链表存储表示*/typedefstructBTNode{chardata;/*结点数据*/structBTNode*lchild;/*左孩子指针*/structBTNode*rchild;/*右孩子指针*/}*BiTree;/*非递归遍历辅助队列*/typedefstruct{BiTreedata[MAX];intfront,rear;/*先序遍历创建二叉树*//*先序遍历创建二叉树*//*先序遍历二叉树*//*中序遍历二叉树*//*后序遍历二叉树*//*先序遍历的非递归算法*//*中序遍历的非递归算法*//*后序遍历的非递归算法*/voidcreateBiTree(BiTree*t);voidPreOrder(BiTreep);voidInOrder(BiTreep);voidPostOrder(BiTreep);voidRPreorder(BiTreep);voidRInorder(BiTreep);voidRPostorder(BiTreep);/*以后序遍历的方式复制二叉树/*以后序遍历的方式复制二叉树*//*交换二叉树的结点的左右孩子*//*利用循环队列实现层次遍历*//*统计二叉树叶子结点（递归）*//*释放二叉树*//*扔掉存在键盘缓冲区的输入结束回车符*//*子树为空则返回*/intdepth(BiTreet);/*求二叉树的深度算法*/BiTreegettreenode(charx,BiTreelptr,BiTreerptr);/*后序复制二叉树-建立结点*/BiTreecopytree(BiTreet);BiTreeswap(BiTreeb);voidccOrder(BiTreet);intLeaves(BiTreet);voidrelease(BiTreet);/*先序遍历创建二叉树*/voidcreateBiTree(BiTree*t){chars;BiTreeq;s=getchar();getchar();if(s=='#'){*t=NULL;return;}q=(BiTree)malloc(sizeof(structBTNode));if(q==NULL){exit(0);}q->data=s;*t=q;createBiTree(&q->lchild);/*递归建立左子树*/createBiTree(&q->rchild);/*递归建立右子树*/}/*createBiTree*//*先序遍历二叉树，补充递归算法*/voidPreOrder(BiTreep){if(p!=NULL){PreOrder(p->lchild);PreOrder(p->rchild);}}/*PreOrder*//*中序遍历二叉树，补充递归算法*/voidInOrder(BiTreep){if(p!=NULL){InOrder(p->lchild);InOrder(p->rchild);}}/*InOrder*//*后序遍历二叉树，补充递归算法*/voidPostOrder(BiTreep){if(p!=NULL){PostOrder(p->lchild):PostOrder(p->rchild);}}/*PostOrder*//*先序遍历的非递归算法*/voidRPreorder(BiTreep){BiTreestack[MAX],q;inttop=0,i;for(i=0;i<MAX;i++)stack[i]=NULL;/*初始化树结点*/q=p;while(q!=NULL){if(q->rchild!=NULL)stack[top++]=q->rchild;/*右指针进栈*/if(q->lchild!=NULL)q=q->lchild;/*顺着左指针继续向下*/elseif(top>0)q=stack[--top];/*左子树访问完，出栈继续访问右子树结点*/elseq=NULL;}}/*RPreorder*//*中序遍历的非递归算法*/voidRInorder(BiTreep){BiTreestack[MAX],q;inttop=0,i;for(i=0;i<MAX;i++)stack[i]=NULL;/*初始化树结点*/q=p;while(q!=NULL){if(q->rchild!=NULL)stack[top++]=q->rchild;/*右指针进栈*/if(q->lchild==NULL)elsestack[top++]=q->lchild;/*左指针进栈*/q=q->lchild;/*顺着左指针继续向下*/elseif(top>0)q=stack[--top];/*左子树访问完，出栈继续访问右子树结点*/elseq=NULL;}}/*RInorder*//*后序遍历的非递归算法*/voidRPostorder(BiTreep){BiTreestack[MAX],q;inti,top=0,flag[MAX];for(i=0;i<MAX;i++)/*初始化栈*/{stack[i]=NULL;flag[i]=0;}q=p;while(q!=NULL||top!=0){if(q!=NULL)/*当前结点进栈，先遍历其左子树*/{stack[top]=q;flag[top]=0;top++;q=q->lchild;}else{while(top){if(flag[top-1]==0)/*遍历结点的右子树*/{q=stack[top-1];q=q->rchild;flag[top-1]=1;break;}else{q=stack[--top];遍历结点*/}}}if(top==0)break;}}/*RPostorder*//*求二叉树的深度算法，补充递归算法*/intdepth(BiTreet){intrd,ld;if(!t)return0;else{rd=depth(B->lchild);ld=depth(B->rchild);if(rd>ld)returnld+1;elsereturnrd+1;}}/*depth*//*建立结点*/BiTreegettreenode(charx,BiTreelptr,BiTreerptr){BiTreet;t=(BiTree)malloc(sizeof(structBTNode));t->data=x;t->lchild=lptr;t->rchild=rptr;return(t);}/*gettreenode*//*以后序遍历的方式递归复制二叉树*/BiTreecopytree(BiTreet){BiTreenewlptr,newrptr,newnode;if(t==NULL)returnNULL;if(t->lchild!=NULL)newlptr=copytree(t->lchild);elsenewlptr=NULL;if(t->rchild!=NULL)newrptr=copytree(t->rchild);elsenewrptr=NULL;newnode=gettreenode(t->data,newlptr,newrptr);return(newnode);}/*copytree*//*交换二叉树的结点的左右孩子*/BiTreeswap(BiTreeb){BiTreet,t1,t2;if(b==NULL)t=NULL;else{t=(BiTree)malloc(sizeof(structBTNode));t->data=b->data;t1=swap(b->lchild);/*递归交换左子树上的结点*/t2=swap(b->rchild);/*递归交换右子树上的结点*/t->lchild=t2;/*交换根t的左右子树*/t->rchild=t1;}return(t);}/*swap*//*利用循环队列实现层次遍历*/voidccOrder(BiTreet){}/*ccOrder*///定义队列typedefstructqueue{BT*base;intfront;intrear;}queue;//队列实现voidQueueStart(queue&Q)//队列的初始化{Q.base=(BT*)malloc(size*sizeof(BT));if(!Q.base)exit(0);Q.front=0;Q.rear=0;}voidQueueInt(queue&Q,BT&p)//入队{if((Q.rear+1)%size==Q.front)return;Q.base[Q.rear]=p;Q.rear=(Q.rear+1)%size;}voidQueueOut(queue&Q,BT&p)//出队{if(Q.rear==Q.front)return;p=Q.base[Q.front];Q.front=(Q.front+1)%size;}/*统计二叉树叶子结点，补充递归算法*/intLeaves(BiTreet,intsum){if(t){if(t->lchild==NULL&&t->rchild==NULL){sum++;}sum=Leaves(t->lchild,sum);sum=Leaves(t->rchild,sum);}return(sum);}/*Leaves*//*释放二叉树*/voidrelease(BiTreet){if(t!=NULL){release(t->lchild);release(t->rchild);free(t);}}/*release*/intmain(){BiTreet=NULL,copyt=NULL;intselect;do{按先序序列建立二叉树遍历二叉树(三种递归方法)遍历二叉树(三种非递归方法)层次遍历二叉树输出二叉树的深度统计二叉树的叶子结点数(递归)后序遍历方式复制一棵二叉树交换二叉树所有结点的左右孩子getchar();switch(select){case1:按先序序列建立二叉树请依次输入结点序列：createBiTree(&t);if(t!=NULL)二叉树创建成功！else二叉树未创建成功！break;case2:遍历二叉树(三种递归方法)先序遍历序列PreOrder(t);中序遍历序列InOrder(t);后序遍历序列PostOrder(t);break;case3:遍历二叉树(三种非递归方法)先序遍历的非递归RPreorder(t);中序遍历的非递归RInorder(t);后序遍历的非递归RPostorder(t);break;case4:层次遍历二叉树按层次遍历ccOrder(t);break;case5:输出二叉树的深度二叉树的深度break;case6:统计二叉树的叶子结点数(递归)叶子结点数为：break;case7:后序遍历方式复制一棵二叉树copyt=copytree(t);if(copyt!=NULL){先序递归遍历复制的二叉树PreOrder(copyt);}else复制失败！break;case8:交换二叉树所有结点的左右孩子先序递归遍历交换后的二叉树PreOrder(swap(t));break;case0:release(t);/*释放二叉树*/break;default:break;}}while(select);return0;}2、编写程序exp6_2.c，实现哈夫曼树的建立和哈夫曼编码。若有一组字符序列{a,c,e,i,s,t,w},对应的出现频率为{10,1,15,12,3,4,13}。以此序列创建哈夫曼树和哈夫曼编码。回答下列问题，补充完整程序，并调试运行验证结果。构造该序列的哈夫曼树，画出哈夫曼树的形态。(以结点值左小右大的原则)写出对应的哈夫曼编码。a(111)c(11010)e(10)i(00)s(11011)t(1100)w(01)计算编码的WPL。WPL=(1+3)*5+4*4+10*3+(12+13+15)*2=146exp6_2.c程序代码参考如下：#include<stdio.h>#defineMAXVALUE10000/*定义最大权值*/#defineMAXLEAF30/*定义哈夫曼树中叶子结点个数*/#defineMAXNODEMAXLEAF*2-1#defineMAXBIT10/*定义哈夫曼编码的最大长度*/

typedefstruct/*哈夫曼编码结构*/{intbit[MAXBIT];intstart;}/*哈夫曼树结点结构/*哈夫曼树结点结构*/typedefstruct{chardata;intweight;intparent;intlchild;intrchild;}HNodeType;voidHuffmanTree(HNodeTypeHuffNode[],int*hn);voidHuffmanCode(HNodeTypeHuffNode[],HCodeTypeHuffCode[],intn);voidHuffmanTree(HNodeTypeHuffNode[],int*hn)/*哈夫曼树的构造算法*/{inti,j,m1,m2,x1,x2,n;getchar();/*输入叶子结点个数*/for(i=0;iv2*n-l;i++)/*数组HuffNode[]初始化*/{HuffNode[i].data=O;HuffNode[i].weight=O;HuffNode[i].parent=-1;HuffNode[i].lchild=-1;HuffNode[i].rchild=-1;}for(i=0;i<n;i++){/*输入n个叶子结点的权值*/getchar();}for(i=0;i<n-1;i++)/*构造哈夫曼树*/{m1=m2=MAXVALUE;x1=x2=0;for(j=0;j<n+i;j++){if(HuffNode[j].weight<m1&&HuffNode[j].parent==-1){m2=m1;x2=x1;m1=HuffNode[j].weight;x1=j;}elseif(HuffNode[j].weight<m2&&HuffNode[j].parent==-1){m2=HuffNode[j].weight;x2=j;}}/*将找出的两棵子树合并为一棵子树*/HuffNode[x1].parent=n+i;HuffNode[x2].parent=n+i;HuffNode[n+i].weight=HuffNode[xl].weight+Hu