《数据结构与算法》实验指导与报告书

1、常熟理工学院数据结构与算法实验指导与报告书2017-2018学年第一学期专业：物联网工程实验名称：二叉树实验地点：N6-210指导教师：聂盼红计算机科学与工程学院2017精选范本，供参考!实验六二叉树【实验目的】1、掌握二叉树的基本存储表示。2、掌握二叉树的遍历操作实现方法（递归和非递归方法）3、理解并实现二叉树的其他基本操作。4、掌握二叉树的重要应用-哈夫曼编码的实现。【实验学时】4-6学时【实验预习】回答以下问题：1、二叉树的二叉链表存储表示。/*-叉树的叉链表存储表木-*/typedefstructBTNodechardata;/*结点数据*/structBTNode*lchild;/*

2、左孩子指针*/structBTNode*rchild;/*右孩子指针*/*BiTree;2、二叉树的三种基本遍历方式。/*先序遍历二叉树，补充递归算法*/voidPreOrder(BiTreep)if(p!=NULL);printf("%c”,p->data);/访问根节点PreOrder(p->lchild);先序遍历左子数PreOrder(p->rchild);先序遍历右子数/*PreOrder*/*中序遍历二叉树，补充递归算法*/voidInOrder(BiTreep)if(p!=NULL);InOrder(p->lchild);/中序遍历左子数prin

3、tf("%c",p->data);访问根节点InOrder(p->rchild);中序遍历右子数/*InOrder*/*后序遍历二叉树，补充递归算法*/voidPostOrder(BiTreep)if(p!=NULL);PostOrder(p->lchild);后序遍历左子数PostOrder(p->rchild);后序遍历右子数printf("%c",p->data);访问根节点/*PostOrder*/3、解释哈夫曼树和带权路径长度WPL。哈夫曼树，是指权值为W1、W2、.Wn的n个叶节点所构成的二叉树中带权路径长度最小

4、的二叉树。从树根结点到到该结点之间的路径长度与该结点上权的乘积称为结点的带权路径长度，通常记作：WPL=2(n,i=1)WiLi【实验内容和要求】1、编写程序exp6_1.c,实现二叉树的链式存储及基本操作。以下图所示的二叉树实现二叉树的二叉链表存储及基本操作，回答下列问题，补充完整程序，并调试运行验证结果。u.1Al(1)按照先序序列建立该二叉树。读入的字符序列应为：A,B,C,*,*,D,E,*,G,*,;F,*,*,*(*表示空指针)。(2)该二叉树的三种遍历序列：先序序列：A,B,C,D,E,G,F;中序序列：C,B,E,G,D,F,A;后序序列：C,G,E,F,D,B,A;(3)按层

5、次遍历该二叉树，得到的序列为：A,B,C,D,E,F,G(4)该二叉树的深度为5。(5)该二叉树的叶子结点数为：3。(画出新二叉树的图)(6)交换该二叉树所有结点的左右次序得到的新二叉树为:(7)新二叉树的三种遍历序列分别为：先序序列：A,B,D,C,F,G,E;中序序列：D,B,F,G,C,E,A;后序序列：D,G,F,E,C,B,A;exp6_1.c参考程序如下：#include<stdio.h>#include<malloc.h>#defineMAX20/*-叉树的叉链表存储表木-*/typedefstructBTNodechardata;/*结点数据*/stru

6、ctBTNode*lchild;/*左孩子指针*/structBTNode*rchild;/*右孩子指针*/*BiTree;/*-非递归遍历辅助队列-*/typedefstructSqQueueBiTreedataMAX;intfront,rear;SqQueue;/*先序遍历创建二叉树*/*先序遍历二叉树*/*中序遍历二叉树*/*后序遍历二叉树*/voidcreateBiTree(BiTree*t);voidPreOrder(BiTreep);voidInOrder(BiTreep);voidPostOrder(BiTreep);voidRPreorder(BiTreep);/*先序遍历的非

7、递归算法*/voidRInorder(BiTreep);/*中序遍历的非递归算法*/voidRPostorder(BiTreep);/*后序遍历的非递归算法*/intdepth(BiTreet);/*求二叉树的深度算法*/BiTreegettreenode(charx,BiTreelptr,BiTreerptr);/*后序复制二叉树-建立Z点*/BiTree copytree(BiTree t);BiTree swap(BiTree b);void ccOrder(BiTree t);int Leaves(BiTree t);void release(BiTree t);/*以后序遍历的方式复

8、制二叉树*/*交换二叉树的结点的左右孩子*/*利用循环队列实现层次遍历*/*统计二叉树叶子结点（递归）*/*释放二叉树*/*先序遍历创建二叉树*/voidcreateBiTree(BiTree*t)chars;BiTreeq;printf("npleaseinputdata:");s=getchar();getchar();/*扔掉存在键盘缓冲区的输入结束回车符*/if(s='#')/*子树为空则返回*/*t=NULL;return;elseq=(BiTree)malloc(sizeof(structBTNode);if(q=NULL)printf(&quo

9、t;Memoryallocfailure!");exit(0);q->data=s;*t=q;createBiTree(&q->lchild);/*递归建立左子树*/createBiTree(&q->rchild);/*递归建立右子树*/*createBiTree*/*先序遍历二叉树，补充递归算法*/voidPreOrder(BiTreep)if(p!=NULL)printf("%c”,p->data);/访问根节点PreOrder(p->lchild);先序遍历左子数PreOrder(p->rchild);先序遍历右子数

10、/*PreOrder*/*中序遍历二叉树，补充递归算法*/voidInOrder(BiTreep)if(p!=NULL)InOrder(p->lchild);/中序遍历左子数printf("%c”,p->data);/访问根节点InOrder(p->rchild);中序遍历右子数/*InOrder*/*后序遍历二叉树，补充递归算法*/voidPostOrder(BiTreep)if(p!=NULL)PostOrder(p->lchild);后序遍历左子数PostOrder(p->rchild);后序遍历右子数printf("%c”,p->

11、data);/访问根节点/*PostOrder*/*先序遍历的非递归算法*/voidRPreorder(BiTreep)BiTreestackMAX,q;inttop=0,i;for(i=0;i<MAX;i+)stacki=NULL;/*初始化栈*/q=p;while(q!=NULL)printf("%c",q->data);if(q->rchild!=NULL)stacktop+=q->rchild;/*右指针进栈*/if(q->lchild!=NULL)q=q->lchild;/*顺着左指针继续向下*/elseif(top>0)

12、*/q=stack-top;/*左子树访问完，出栈继续访问右子树结点elseq=NULL;/*RPreorder*/*中序遍历的非递归算法*/voidRInorder(BiTreep)BiTreestackMAX,q;定义节点栈和搜索指针inttop=0;q=p；dowhile(q)/左链所有节点入栈stacktop+=q;q=q->lchild;if(top>0)q=stack-top;printf("%c",q->data);访问根q=q->rchild;while(q|top!=0);/*RInorder*/*后序遍历的非递归算法*/voidR

13、Postorder(BiTreep)BiTreestackMAX,q;inti,top=0,flagMAX;for(i=0;i<MAX;i+)/*初始化栈*/stacki=NULL;flagi=0;q=p;while(q!=NULL|top!=0)*/if(q!=NULL)/*当前结点进栈，先遍历其左子树stacktop=q;flagtop=0;top+;q=q->lchild;elsewhile(top)if(flagtop-1=0)/*遍历结点白右子树*/q=stacktop-1;q=q->rchild;flagtop-1=1;break;elseq=stack-top;

14、printf("%c",q->data);/*遍历结点*/if(top=0)break;/*RPostorder*/*求二叉树的深度算法，补充递归算法*/intdepth(BiTreet)intlc,rc;if(t=NULL)return0;若为空树，则返回零elselc=depth(t->lchild);/递归求t的左子树深度rc=depth(t->rchild);/递归求t的右子树深度if(lc>rc)return(lc+1);elsereturn(rc+1);/*depth*/*建立结点*/BiTreegettreenode(charx,BiT

15、reelptr,BiTreerptr)BiTreet;t=(BiTree)malloc(sizeof(structBTNode);t->data=x;t->lchild=Iptr;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

16、;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;elset=(BiTree)malloc(sizeof(structBTNode);t->data=b->data;t1=swap(b->lchild);/

17、*递归交换左子树上的结点*/t2=swap(b->rchild);/*递归交换右子树上的结点*/*交换根t的左右子树*/t->lchild=t2;t->rchild=t1;return(t);/*swap*/*利用循环队列实现层次遍历*/voidccOrder(BiTreet)BiTreep;SqQueueqlist,*q;利用循环队列，实现层次遍历q=&qlist;q->rear=0;q->front=0;初始化队列p=t;if(p!=NULL)printf("%c”,p->data);/访问根节点q->dataq->rear

18、=p;/根节点入队q->rear=(q->rear+1)%MAX;/修改队尾指针while(q->front!=q->rear)p=q->dataq->front;/出队操作q->front=(q->front+1)%MAX;if(p->lchild!=NULL)访问出队节点的左孩子，并且入队printf("%c",p->lchild->data);q->dataq->rear=p->lchild;q->rear=(q->rear+1)%MAX;if(p->rchild!=

19、NULL)访问出队节点的右孩子，并且入队printf("%c",p->rchild->data);q->dataq->rear=p->rchild;q->rear=(q->rear+1)%MAX;/*ccOrder*/*统计二叉树叶子结点，补充递归算法*/intLeaves(BiTreet)if(t=NULL)return0;if(t->lchild=NULL&&t->rchild=NULL)return1;return(Leaves(t->lchild)+Leaves(t->rchild);

20、左子数叶子节点加上右子数叶子结点/*Leaves*/*释放二叉树*/voidrelease(BiTreet)if(t!=NULL)release(t->lchild);release(t->rchild);free(t);/*release*/intmain()BiTreet=NULL,copyt=NULL;intselect;doprintf("n*MENU*n");printf（"1.按先序序列建立二叉树n"）;printf（"2.遍历二叉树（三种递归方法）n"）;printf（"3.遍历二叉树（三种非递归方

21、法）n"）;printf（"4.层次遍历二叉树n"）;printf（"5.输出二叉树的深度n"）;printf（"6.统计二叉树的叶子结点数（递归）n"）;printf（"7.后序遍历方式复制一棵二叉树n"）;printf（"8.交换二叉树所有结点的左右孩子n"）;printf("0.EXIT");printf("n*MENU*n");printf("ninputchoice:");scanf("%d",&

22、amp;select);getchar();switch(select)case 1:printf（"n1-按先序序列建立二叉树：n"）;printf（"请依次输入结点序列：n"）;/BiTreegettreenode(x,&lptr,&rptr);createBiTree(&t);if(t!=NULL)printf("二叉树创建成功！n");elseprintf("二叉树未创建成功！n");break;case 2:printf("n2-遍历二叉树(三种递归方法)：n"

23、);printf("n先序遍历序列：")；PreOrder；printf("n中序遍历序列：")；InOrder(t);printf("n后序遍历序列：")；PostOrder(t);printf("n");break;case 3:printf("n3-遍历二叉树(三种非递归方法)：n");printf("n先序遍历的非递归：")；RPreorder(t);printf("n中序遍历的非递归：")；RInorder；printf("n后序遍历的

24、非递归：")；RPostorder(t);printf("n");break;case 4:printf("n4-层次遍历二叉树：n");printf("n按层次遍历：”)；ccOrder(t);printf("n");break;case 5:printf("n5-输出二叉树的深度：n");printf("n二叉树的深度：d",depth(t);printf("n");break;case 6:printf("n6-统计二叉树的叶子结点数(递归

25、)：n");printf("n叶子结点数为：d",Leaves(t);printf("n");break;case 7:printf("n7-后序遍历方式复制一棵二叉树：n");copyt=copytree(t);if(copyt!=NULL)printf("n先序递归遍历复制的二叉树：")；PreOrder(copyt);elseprintf("n复制失败！");printf("n");break;case 8:printf("n8-交换二叉树所有结点的

26、左右孩子：n");printf("n先序递归遍历交换后的二叉树：")；*/PreOrder(swap(t);/*如需输出中序和后序遍历的结果，增加调用printf("n");break;case0:release(t);/*释放二叉树*/break;default:break;while(select);return0;exp6_1.c实验结果：(1)按照先序序列建立二叉树：xnputtIcek奉先序序冽建立二上请艘次输入结点庠列.pleaseinputdata=apleaseinp”匚data=bple»£R'&q

27、uot;iripii.trdai=h.：cpleatseinputdata：1!pleaseinputdata01名足髭倍inj»iitria七%：dpleaseinputpleaeein)>utd*七鼻=itT>leaseinputd矶td：gjjleA&cliipubdatii-ttpleaseififiiitd以肥atilpleaseinputdatdi：fplDaitoxnputdaltai*1tpleaseinvutdata-ttpl匕4对修JjkpUUddCd-tt一叉洞创建成功I(2)该二叉树的三种递归遍历序列为:Inputchoice-2”遍后二叉

28、树(三种递归方法)-a be de'jff F =c h&sdE z segG £dba(3)遍历二叉树(三种非递归方法)input chulee-3J遍历二式树(三种非递归方法)=历历历遍遍遍先中后的的的力石，百逸凰剧-h_lLr.二：cgcfdba(4)层次遍历二叉树：inpuitchoicc：44-层次遍历二叉树二按层次遍历旧如日匚£目(5)输出二叉树的深度£niputcliaice：=>A输出二叉树的深度，二叉树的深度逐(6)统计二叉树的叶子结点数(递归)XTIpULt；!JLGC=6统计一叉树的叶子结点数(递归)：卜子结点数为：3|

29、(7)后序遍历方式复制一棵二叉树inpLi/tchcice：后序遍历方式复制一棵二翼树=先序递归遍历复制的二叉树ebcM复(8)交换二叉树所有结点的左右孩子xnpotcliaice18交换二叉树所有皓点的左右落子工先序递归遍历交执后的二翼树媪京"2、编写程序exp6_2.c,实现哈夫曼树的建立和哈夫曼编码。若有一组字符序列a,c,e,i,s,t,w,对应的出现频率为10,1,15,12,3,4,13。以此序列创建哈夫曼树和哈夫曼编码。回答下列问题，补充完整程序，并调试运行验证结果。(1) 构造该序列的哈夫曼树，画出哈夫曼树的形态。(以结点值左小右大的原则)T658T425T533T3

30、18e15i12w13t28a 10t4T14cls 3(2) 写出对应的哈夫曼编码。a的编码为111,c的编码为11000,e的编码为10,i的编码为00,s的编码为11001,t的编码为1101,w的编码为01(3) 计算编码的WPL。WPL=3*10+5*1+2*15+2*12+5*3+4*4+2*13=146exp6_2.c程序代码参考如下：#include<stdio.h># defineMAXVALUE10000/*定义最大权值*/# defineMAXLEAF30/*定义哈夫曼树中口t子结点个数*/# defineMAXNODEMAXLEAF*2-1# defineM

31、AXBIT10/*定义哈夫曼编码的最大长度*/typedefstruct/*哈夫曼编码结构*/intbitMAXBIT;intstart;HCodeType;typedefstruct/*哈夫曼树结点结构*/chardata;intweight;intparent;intIchild;intrchild;HNodeType;voidHuffmanTree(HNodeTypeHuffNode,int*hn);voidHuffmanCode(HNodeTypeHuffNode口,HCodeTypeHuffCode口,intn);voidHuffmanTree(HNodeTypeHuffNode,i

32、nt*hn)/*哈夫曼树的构造算法*/inti,j,m1,m2,x1,x2,n;printf("n:");scanf("%d",&n);getchar();/*输入叶子结点个数*/for(i=0;i<2*n-1;i+)/*数组HuffNode初始化*/HuffNodei.parent=-1;HuffNodei.lchild=-1;HuffNodei.rchild=-1;printf("HuffNode:n");for(i=0;i<n;i+)scanf("%c,%d",&HuffNodei

33、.data,&HuffNodei.weight);/*输入n个叶子结点的权值*/getchar();for(i=0;i<n-1;i+)/*构造哈夫曼树*/m1=m2=MAXVALUE;x1=x2=0;for(j=0;j<n+i;j+)if(HuffNodej.weight<m1&&HuffNodej.parent=-1)m2=m1;x2=x1;m1=HuffNodej.weight;x1=j；elseif(HuffNodej.weight<m2&&HuffNodej.parent=-1)m2=HuffNodej.weight;x2

34、=j;/*将找出的两棵子树合并为一棵子树*/HuffNodex1.parent=n+i;HuffNodex2.parent=n+i;HuffNoden+i.weight=HuffNodex1.weight+HuffNodex2.weight;HuffNoden+i.lchild=x1;HuffNoden+i.rchild=x2;*hn=n;voidHuffmanCode(HNodeTypeHuffNode,HCodeTypeHuffCode,intn)/*生成哈夫曼编码*/HCodeTypecd;inti,j,c,p;for(i=0;i<n;i+)/*求每个叶子结点的哈夫曼编码*/cd.start=n-1;c=i;p=HuffNodec.parent;while(p!=-1)/*由叶