树和二叉树实验报告

..树和二叉树一、实验目的1.掌握二叉树的结构特征，以及各种存储结构的特点及适用范围。2.掌握用指针类型描述、访问和处理二叉树的运算。二、实验要求1.认真阅读和掌握本实验的程序。2.上机运行本程序。3.保存和打印出程序的运行结果，并结合程序进行分析。4.按照二叉树的操作需要，重新改写主程序并运行，打印出文件清单和运行结果。三、实验内容1.输入字符序列，建立二叉链表。2.按先序、中序和后序遍历二叉树（递归算法）。3.按某种形式输出整棵二叉树。4.求二叉树的高度。5.求二叉树的叶节点个数。6.交换二叉树的左右子树。7.借助队列实现二叉树的层次遍历。8.在主函数中设计一个简单的菜单，分别调试上述算法。..为了实现对二叉树的有关操作，首先要在计算机中建立所需的二叉树。建立二叉树有各种不同的方法。一种方法是利用二叉树的性质5来建立二叉树，输入数据时要将节点的序号（按满二叉树编号）和数据同时给出：（序号，数据元素0）。另一种方法是主教材中介绍的方法，这是一个递归方法，与先序遍历有点相似。数据的组织是先序的顺序，但是另有特点，当某结点的某孩子为空时以字符“#”来充当，也要输入。若当前数据不为“#”，则申请一个结点存入当前数据。递归调用建立函数，建立当前结点的左右子树。四、解题思路1、先序遍历：○1访问根结点，○2先序遍历左子树，○3先序遍历右子树2、中序遍历：○1中序遍历左子树，○2访问根结点，○3中序遍历右子树3、后序遍历：○1后序遍历左子树，○2后序遍历右子树，○3访问根结点4、层次遍历算法：采用一个队列q，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进后出，所以能够达到按层次遍历二叉树的目的。五、程序清单#includestdio.h#includestdlib.h#defineM100typedefcharEtype;//定义二叉树结点值的类型为字符型typedefstructBiTNode//树结点结构{Etypedata;structBiTNode*lch,*rch;}BiTNode,*BiTree;..BiTreeque[M];intfront=0,rear=0;//函数原型声明BiTNode*creat_bt1();BiTNode*creat_bt2();voidpreorder(BiTNode*p);voidinorder(BiTNode*p);voidpostorder(BiTNode*p);voidenqueue(BiTree);BiTreedelqueue();voidlevorder(BiTree);inttreedepth(BiTree);voidprtbtree(BiTree,int);voidexchange(BiTree);intleafcount(BiTree);voidpaintleaf(BiTree);BiTNode*t;intcount=0;//主函数voidmain(){charch;intk;do{printf(\n\n\n);printf(\n===================主菜单===================);printf(\n\n1.建立二叉树方法1);printf(\n\n2.建立二叉树方法2);printf(\n\n3.先序递归遍历二叉树);printf(\n\n4.中序递归遍历二叉树);printf(\n\n5.后序递归遍历二叉树);printf(\n\n6.层次遍历二叉树);printf(\n\n7.计算二叉树的高度);printf(\n\n8.计算二叉树中叶结点个数);printf(\n\n9.交换二叉树的左右子树);printf(\n\n10.打印二叉树);printf(\n\n0.结束程序运行);printf(\n============================================);printf(\n请输入您的选择(0,1,2,3,4,5,6,7,8,9,10));scanf(%d,&k);switch(k){case1:t=creat_bt1();break;//调用性质5建立二叉树算法..case2:printf(\n请输入二叉树各结点值:);fflush(stdin);t=creat_bt2();break;//调用递归建立二叉树算法case3:if(t){printf(先序遍历二叉树:);preorder(t);printf(\n);}elseprintf(二叉树为空!\n);break;case4:if(t){printf(中序遍历二叉树:);inorder(t);printf(\n);}elseprintf(二叉树为空!\n);break;case5:if(t){printf(后序遍历二叉树:);postorder(t);printf(\n);}elseprintf(二叉树为空!\n);break;case6:if(t){printf(层次遍历二叉树：);levorder(t);printf(\n);}elseprintf(二叉树为空！\n);break;case7:if(t){printf(二叉树的高度为：%d,treedepth(t));printf(\n);}elseprintf(二叉树为空！\n);break;case8:if(t){printf(二叉树的叶子结点数为：%d\n,leafcount(t));printf(二叉树的叶结点为：);paintleaf(t);printf(\n);}elseprintf(二叉树为空！\n);break;..case9:if(t){printf(交换二叉树的左右子树：\n);exchange(t);prtbtree(t,0);printf(\n);}elseprintf(二叉树为空！\n);break;case10:if(t){printf(逆时针旋转90度输出的二叉树：\n);prtbtree(t,0);printf(\n);}elseprintf(二叉树为空！\n);break;case0:exit(0);}//switch}while(k=1&&k=10);printf(\n再见！按回车键，返回…\n);ch=getchar();}//main//利用二叉树性质5，借助一维数组V建立二叉树BiTNode*creat_bt1(){BiTNode*t,*p,*v[20];inti,j;Etypee;/*输入结点的序号i、结点的数据e*/printf(\n请输入二叉树各结点的编号和对应的值（如1，a）：);scanf(%d,%c,&i,&e);while(i!=0&&e!='#')//当i为0，e为'#'时，结束循环{p=(BiTNode*)malloc(sizeof(BiTNode));p-data=e;p-lch=NULL;p-rch=NULL;v[i]=p;if(i==1)t=p;//序号为1的结点是根else{j=i/2;if(i%2==0)v[j]-lch=p;//序号为偶数，作为左孩子elsev[j]-rch=p;//序号为奇数，作为右孩子}..printf(\n请继续输入二叉树各结点的编号和对应的值：);scanf(%d,%c,&i,&e);}return(t);}//creat_bt1;//模仿先序递归遍历方法，建立二叉树BiTNode*creat_bt2(){BiTNode*t;Etypee;scanf(%c,&e);if(e=='#')t=NULL;//对于'#'值，不分配新结点else{t=(BiTNode*)malloc(sizeof(BiTNode));t-data=e;t-lch=creat_bt2();//左孩子获得新指针值t-rch=creat_bt2();//右孩子获得新指针值}return(t);}//creat_bt2//先序递归遍历二叉树voidpreorder(BiTNode*p){if(p){printf(%3c,p-data);preorder(p-lch);preorder(p-rch);}}//preorder//中序递归遍历二叉树voidinorder(BiTNode*p){if(p){inorder(p-lch);printf(%3c,p-data);inorder(p-rch);}}//inorder//后序递归遍历二叉树voidpostorder(BiTNode*p){if(p){postorder(p-lch);postorder(p-rch);printf(%3c,p-data);}..}//postordervoidenqueue(BiTreeT){if(front!=(rear+1)%M){rear=(rear+1)%M;que[rear]=T;}}BiTreedelqueue(){if(front==rear)returnNULL;front=(front+1)%M;return(que[front]);}voidlevorder(BiTreeT)//层次遍历二叉树{BiTreep;if(T){enqueue(T);while(front!=rear){p=delqueue();printf(%3d,p-data);if(p-lch!=NULL)enqueue(p-lch);if(p-rch!=NULL)enqueue(p-rch);}}}inttreedepth(BiTreebt)//计算二叉树的高度{inthl,hr,max;if(bt!=NULL){hl=treedepth(bt-lch);hr=treedepth(bt-rch);max=(hlhr)?hl:hr;return(max+1);}elsereturn(0);}voidprtbtree(BiTreebt,intlevel)//逆时针旋转90度输出二叉树树形{intj;..if(bt){prtbtree(bt-rch,level+1);for(j=0;j=6*level;j++)printf();printf(%c\n,bt-data);prtbtree(bt-lch,level+1);}}voidexchange(BiTreebt)//交换二叉树左右子树{BiTreep;if(bt){p=bt-lch;bt-lch=bt-rch;bt-rch=p;exchange(bt-lch);exchange(bt-rch);}}intleafcount(BiTreebt)//计算叶结点数{if(bt!=NULL){leafcount(bt-lch);leafcount(bt-rch);if((bt-lch==NULL)&&(bt-rch==NULL))count++;}return(count);}voidpaintleaf(BiTreebt)//输出叶结点{if(bt!=NULL){if(bt-lch==NULL&&bt-rch==NULL)printf(%3c,bt-data);paintleaf(bt-lch);paintleaf(bt-rch);}}图11.2所示二叉树的输入数据顺序应该是：abd#g###ce#h##f##。..图11.2二叉树示意图运行结果：===================主菜单===================1.建立二叉树方法12.建立二叉树方法23.先序递归遍历二叉树4.中序递归遍历二叉树5.后序递归遍历二叉树6.层次遍历二叉树7.计算二叉树的高度8.计算二叉树中叶结点个数9.交换二叉树的左右子树10.打印二叉树0.结束程序运行============================================请输入您的选择(0,1,2,3,4,5,6,7,8,9,10)1请输入