北航计软实验报告实验二

实验报告实验名称二叉树班级学号姓名成绩实验概述：【实验目的及要求】掌握二叉树的存储结构【实验原理】（1）二叉树的链式存储结构二叉树的每一个结点i有三个域：值域V（i），左链域L（i），右链域R（i）。分别用三个一维数组表示它们，并用头指针HBT指向二叉树的根结点。（2）按层次输出所有结点设置一个容量足够大的循环队列（可以用一个首尾相接的一维数组模拟）。初始时，将根结点序号入队。然后每次从队列中退出一个结点序号，将此结点的值及左右链指针输出，且依次将此结点的左右链指针入队。这个过程一直进行到队列空为止。设循环队列数组为cq（1：m），其头尾指针分别为front与rear，则按层次输出所有结点的算法如下：IFHBT=0THENRETURN“THISTREEISEMPTY”Frontm,rearmADD(cq,HBT,front,rear)WHILEfrontrearDO{DEL(cq,i,front,rear)OUTPUT(L(i),V(i),R(i))IFL(i)0THENADD(cq,L(i),front,rear)IFR(i)0THENADD(cq,R(i),front,rear)}RETURN在这个算法中的ADD和DEL分别为入队和退队运算的两个过程,其算法(不考虑溢出情况)如下：ADD（cq，i，front，rear）rearrear+1IFrear=m+1THENrear1cq（rear）iRETURNDEL(cq,i,front,rear)frontfront+1IFfront=m+1THENfont1icq(front)RETURN（3）输出所有叶子结点设置一个容量足够大的栈S（可以用一个一维数组模拟它，栈底在数组的第一个元素处）。具体过程是：从根结点开始扫描二叉树，如果扫描的当前结点的左右均为零，则输出次叶子结点；否则将非零的右指针和左指针值推入堆栈。然后从栈中退出一个结点序号重新进行这个过程，直至栈空为止。其算法如下：IFHBT=0THENRETURN“THISTREEISEMTPY”top0PUSH（S，HBT，top）WHILEtop0DO{POP（S，i，top）IF（L（i）=0）and（R（i）=0）THENOUTPUTV（i）ELSE{IFR（i）0THENPUSH（S，R（i），top） IFL（i）0THENPUSH（S，L（i），top）}}RETURN（4）将所有左右子树值交换这个问题的处理和输出所有叶子结点的问题很类似，只要将非叶子结点的左右指针交换即可，其算法如下：IFHBT=0THENRETURN“THISTREEISEMPTY”top0PUSH（S，HBT，top）WHILEtop0DO{POP（S，i，top）IF（L（i）0）or（R（i）0）THEN{L（i）R（i）IFL（i）0THENPUSH（S，L（i），top）IFR（i）0THENPUSH（S，R（i），top）}}RETURN【实验环境】（使用的软硬件）硬件：PC软件：VC++6.0实验内容：【实验方案设计】1．对给定二叉树用链式链式存储结构；利用队列与栈对二叉树进行运算。2．按层次输出所有结点。3．输出所有叶子结点。4．将所有左右子树值交换。【实验过程】（实验步骤、记录、数据、分析）（一）实验步骤1．分别编制实验内容中题2、3、4的三个子程序。2．以上图所示的二叉树为例编制主程序，实现下述功能，并运行这个程序。（1）输入二叉树用链式结构存储；（2）调用题2的子程序，并输出结果；（3）调用题3的子程序，并输出结果；（4）调用题4的子程序，并输出结果；3．自行设计一棵二叉树，重复步骤2。4．整理程序清单与所有结果，并写出实验报告。（二）程序清单#include<stdio.h>#include<stdlib.h>structtree{intnum;structtree*left;structtree*right;};inta[50]={0};structtree*build(inti){structtree*n;n=(structtree*)malloc(sizeof(structtree));n->num=a[i];if(a[2*i]!=0)n->left=build(2*i);elsen->left=NULL;if(a[2*i+1]!=0)n->right=build(2*i+1);elsen->right=NULL;return(n);}structtree*head;intbuild_binary_tree(){FILE*fi;inti=1;charfile_name[20];printf("请输入存放满二叉树数据的文件名称:");scanf("%s",file_name);fi=fopen(file_name,"r");if(fi==NULL){printf("文件读取失败，名为“%s”的文件不存在！\n",file_name);return(0);}else{while(!feof(fi)){fscanf(fi,"%d",&a[i]);i=i+1;}fclose(fi);head=build(1);printf("文件读取成功，已用链式存储方式构建二叉树。");return(1);}}#definem100voidadd(structtree**cq,structtree*n,int*pfront,int*prear){*prear=*prear+1;if(*prear==m+1)*prear=1;cq[*prear]=n;}voiddel(structtree**cq,structtree**ptemp,int*pfront,int*prear){*pfront=*pfront+1;if(*pfront==m+1)*pfront=1;*ptemp=cq[*pfront];}voidfunc_2(structtree*head){if(head==0)printf("此二叉树为空！\n");else{structtree*cq[m],*temp,**ptemp=&temp;intfront=m,rear=m,*pfront=&front,*prear=&rear;printf("(2)按层次输出所有节点：\n");add(cq,head,pfront,prear);while(front!=rear){del(cq,ptemp,pfront,prear);printf("%d",temp->num);if(temp->left!=NULL){printf("左节点:%d",temp->left->num);add(cq,temp->left,pfront,prear);}elseprintf("无左节点");if(temp->right!=NULL){printf("右节点:%d",temp->right->num);add(cq,temp->right,pfront,prear);}elseprintf("无右节点");printf("");printf("\n");}printf("\n");}}voidpush(structtree**S,structtree*n,int*ptop){*ptop=*ptop+1;S[*ptop]=n;}voidpop(structtree**S,structtree**ptemp,int*ptop){*ptemp=S[*ptop];*ptop=*ptop-1;}voidfunc_3(structtree*head){if(head==0)printf("此二叉树为空！\n");else{inti=1;structtree*S[m],*temp,**ptemp=&temp;inttop=0,*ptop=⊤printf("(3)此二叉树的所有叶子结点为:\n");push(S,head,ptop);while(top!=0){pop(S,ptemp,ptop);if((temp->left==NULL)&&(temp->right==NULL))printf("%d",temp->num);else{if(temp->right!=NULL)push(S,temp->right,ptop);if(temp->left!=NULL)push(S,temp->left,ptop);}}printf("\n\n");}}voidfunc_4(structtree*head){if(head==0)printf("此二叉树为空！\n");else{inti=1;structtree*S[m],*temp,**ptemp=&temp,*exchange;inttop=0,*ptop=⊤printf("(4)执行所有左右子树值交换操作。\n操作过程显示如下：\n");push(S,head,ptop);while(top!=0){pop(S,ptemp,ptop);if((temp->left!=NULL)||(temp->right!=NULL)){exchange=temp->left;temp->left=temp->right;temp->right=exchange;printf("交换结点“%d”的左子树与右子树",temp->num);if(temp->left!=NULL)push(S,temp->left,ptop);if(temp->right!=NULL)push(S,temp->right,ptop);}}printf("\n");}func_2(head);}main(){intjudge;while(1){judge=build_binary_tree();if(judge==1){