二叉树的基本操作实验

实验三二叉树的基本运算一、实验目的1、使学生熟练掌握二叉树的逻辑结构和存储结构。2、熟练掌握二叉树的各种遍历算法。二、实验内容[问题描述]建立一棵二叉树，试编程实现二叉树的如下基本操作：1.按先序序列构造一棵二叉链表表示的二叉树T；2.对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；3.求二叉树的深度/结点数目/叶结点数目；(选做)4.将二叉树每个结点的左右子树交换位置。（选做）[基本要求]从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），[测试数据]如输入：ABCффDEфGффFффф（其中ф表示空格字符）则输出结果为先序：ABCDEGF中序：CBEGDFA后序：CGEFDBA层序：ABCDEFG[选作内容]采用非递归算法实现二叉树遍历。三、实验前的准备工作1、掌握树的逻辑结构。2、掌握二叉树的逻辑结构和存储结构。3、掌握二叉树的各种遍历算法的实现。一实验分析本次试验是关于二叉树的常见操作，主要是二叉树的建立和遍历。二叉树的遍历有多种方法，本次试验我采用递归法，递归法比较简单。二概要设计功能实现1.intCreatBiTree(BiTree&T)用递归的方法先序建立二叉树,并用链表储存该二叉树2.intPreTravel(BiTree&T)前序遍历3.intMidTravel(BiTree&T)中序遍历4.intPostTravel(BiTree&T)后序遍历5.intDepth(BiTree&T)//计算树的深度6.inthowmuch(BiTreeT,inth)采用树节点指针数组，用于存放遍历到的元素地址，如果有左孩子，存入地址，j加一，否则没操作，通过访问数组输出层次遍历的结果。k计算叶子数，j为总节点。7.intexchang(BiTree&T)交换左右子树，利用递归，当有左右孩子时才交换三详细设计#includestdio.h#includestdlib.htypedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;H=0printf(%d,j)h==1真printf(%d,k)h==2for(i=0;ij;i++)printf(%c,Q[i]-data)printf(参数错误)真真假假假假intCreatBiTree(BiTree&T){//先序法创建二叉树charch;if((ch=getchar())=='')T=NULL;else{T=(BiTNode*)malloc(sizeof(BiTNode));if(!T)exit(1);T-data=ch;CreatBiTree(T-lchild);CreatBiTree(T-rchild);}return0;}intPreTravel(BiTree&T){//前序遍历if(T){printf(%c,T-data);PreTravel(T-lchild);PreTravel(T-rchild);}return0;}intMidTravel(BiTree&T){//中序遍历if(T){MidTravel(T-lchild);printf(%c,T-data);MidTravel(T-rchild);}return0;}intPostTravel(BiTree&T){//后序遍历if(T){PostTravel(T-lchild);PostTravel(T-rchild);printf(%c,T-data);}return0;}inthowmuch(BiTreeT,inth){BiTNode*Q[100];//树节点指针数组，用于存放遍历到的元素地址if(T==NULL)printf(空的二叉树\n);Q[0]=T;//存入树根inti,k=0;intj=1;//j为总节点for(i=0;ij;i++){if(Q[i]-lchild!=NULL)//如果有左孩子，存入地址，j加一，否则没操作{Q[j]=Q[i]-lchild;j++;}if(Q[i]-rchild!=NULL)//如果有右孩子，存入地址，j加一，否则没操作{Q[j]=Q[i]-rchild;j++;}if(Q[i]-lchild==NULL&&Q[i]-rchild==NULL)k++;//计算叶子数}if(h==0)printf(%d,j);elseif(h==1)printf(%d,k);elseif(h==2){for(i=0;ij;i++)printf(%c,Q[i]-data);}else{printf(参数错误);}return0;}intDepth(BiTree&T)//计算树的深度{intlh,rh;if(NULL==T){return0;}else{lh=Depth(T-lchild);rh=Depth(T-rchild);return(lhrh?lh:rh)+1;}}intexchang(BiTree&T)//交换左右子树{if(T!=NULL){if(T-lchild!=NULL&&T-rchild!=NULL)//当有左右孩子时才交换{chart;t=T-lchild-data;T-lchild-data=T-rchild-data;T-rchild-data=t;//交换数据}exchang(T-lchild);//递归调用exchang(T-rchild);}return0;}intchoose(BiTreeT)//功能选{inta;scanf(%d,&a);if(a==1){printf(先序遍历:);PreTravel(T);}elseif(a==2){printf(中序遍历:);MidTravel(T);}elseif(a==3){printf(后序遍历:);PostTravel(T);}elseif(a==4){printf(层序遍历:);howmuch(T,2);}elseif(a==5){printf(总节点数：);howmuch(T,0);}elseif(a==6){printf(总叶子数：);howmuch(T,1);}elseif(a==7){printf(树的深度：);printf(%d,Depth(T));}elseif(a==8){printf(交换前\n);howmuch(T,2);exchang(T);printf(交换后\n);howmuch(T,2);}elseif(a==9)exit(1);elseprintf(没有这个操作\n);printf(操作完成,请输入下一个操作\n);choose(T);return0;}intmain()//主函数{printf(----------------二叉树的基本操作----------------\n);printf(请先建立二叉树，按先序的方式输入如果数据为空输入空格\n);BiTreeT;//定义二叉树，初始化CreatBiTree(T);choose(T);return0;}四用户手册根据程序的提示按先序输入二叉树，如果数据为空输入空格，然后回车，输入你要进行的操作的序号。1.先序遍历、2中序遍历、3后序遍历、4层次遍历、5总节点数、6总叶子数、7树的深度、8交换左右子树、9结束操作五实验总结通过实验，我熟悉二叉树树的基本操作，掌握二叉树的实现以及实际应用。加深了对二叉树的理解，逐步培养解决实际问题的编程能力以及进一步了解了二叉树。递归的使用，要注意，初始时的状态以及如何使用递归，注意普遍性，思考时从普通的开始。通过这次上机操作，让我明白书本上的程序一定要自己去调试，这样才能将书本程序与老师讲的内容融会贯通，达到温故而知新。六运行结果图（1）ADBCEFG图表1