数据结构：二叉树子系统

*题目：按屏幕提示用前序方法建立一棵二叉树，并能按凹入法显示二叉树结构。编写前序遍历、中序遍历、后序遍历、层次遍历程序。编写求二叉树的叶结点数、总结点数和深度的程序。设计一个选择式菜单，以菜单方式选择下列操作。二叉树子系统建二叉树凹入显示先序遍历中序遍历后序遍历层次遍历求叶子数求结点数求树深度返回请选择菜单号(0—9)*/#include<stdio.h>#include<stdlib.h>typedefstructbTree 〃二叉树结点chardata;〃值域structbTree*Ichild;〃左孩子structbTree*rchild;〃右孩子}BT;BT*createTree();voidshowTree(BT*t);voidpreOrder(BT*t);voidpostOrder(BT*t);voidinOrder(BT*t);voidlevelOrder(BT*t);intleafNum(BT*t);intnodeNum(BT*t);inttreeDepth(BT*t);Function:main()Description:主调函数Input:t:结点指针Return:intQhers:NULL** ♦♦ ********水*********水*水****水*水*水水*水*水*水水*水水水水intnodeNum(BT*t) 〃结点数inti=O;if(t)〃结点不为空(i++；i=nodeNum(t->lchild)4-i;i=nodeNum(t->rchild)+i;)returni;)*来****求*求****水来水**求*求*求****水米水来*来*求*求*****本水水求水水水Function:treeDepth()Description:求二叉树的深度Calls:treeDepth()Input:t:结点指针Return:intQhers:NULL**来**求*求******来来*来*求*求**求*求本*水求水来水本求求*求水永水水水本水水求来inttreeDepth(BT*t) 〃二叉树的深度intIdep,rdep;if(t=NULL)〃结点不为空jreturn0;)else[ldep=treeDepth(t->lchild);rdep=treeDepth(t->rchild);if(ldep>rdep)〃左深度大于右深度)returnldep+1;〃返回左深度的值returnrdep+1;Calls:createTree()showTree()preOrder()postOrder()inOrder()leafNum()levelOrder()nodeNum()treeDepth()**求*水*水**水*求水水水*水水*水**求*水*水**水*求水水水*水水*水voidmain()(BT*t=NULL;intchoice,k=1;while(k)printf（H\n 二叉树子系统\n〃）；prints1——建一叉树printf。'*2—凹入显示printf(n3— 先序遍历printf-4—中序遍历printfC,5—后序遍历printff,6———层次遍历printf(M7—求叶子数printf("*8————求结点数printf("*9————求树深度printf-0-一返回printf*******************************printfjMcfaK***************************1n'）：printf(〃请选择菜单号(0-9):〃);fflush(stdin);scanf("％d”,&choice);switch(choice)(printf(〃请输入根结点('O'表示该结点为空)：〃);t=createTree();printf(〃二叉树建立成功。\n〃)；break;showTree(t);break;printf(〃先序遍历序列：〃);if(t==NULL){printf(〃空。\n〃)；else{preOrder(t);)break;printf(〃中序遍历序列：〃);if(t==NULL))printf(〃空。\n〃)；)else(inOrder(t);}break;printf(〃后序遍历序列：〃);if(t==NULL){printf(〃空。\n〃)；}else{postOrder(t);}break;printf(〃层次遍历序列：〃);if(t==NULL)printf(〃空。\n〃)；}levelOrder(t);}break;printf(〃该二叉树的叶子数：〃)；if(t==NULL)(printf("Oo\n");}else(printf(n%d0\nn,leafNum(t));)break;printf(〃该二叉树的结点数为：〃)；if(t==NULL)(printf("Oo\n");else(printf("%d。\n”,nodeNum(t));)break;printf(〃该二叉树的深度为：〃)；if(t==NULL)(printf("Oo\nH);}elseprintf("%d。\nM,treeDepth(t));}break;case0:k=0;break;default:k=1;break;********来****永*来****永*永****永*永**水*水水水水水水水水求水水求水水水Function:createTree()Description:建立二叉树Calls:createTree()Input: NULLReturn:BT*Qhers:NULL** ** ******************水*水****求*水*水**永*求*水**水水*水BT*createTree() 〃建立二叉树BT*t;charx;getchar();scanf("%cn5&x);〃获取输入的结点值if(x='0‘) 〃输入的值为零，结点为空(t=NULL;)else{t=(BT*)malloc(sizeof(BT));t->data=x; 〃赋值printf(〃请输入结点%c的左孩子：〃,t->data);t->lchild=createTree();〃递归建立左孩子printf(〃请输入结点%c的右孩子：〃,t->data);t->rchild=createTree(); 〃递归调用}returnt;)**********************科"***朴M*******秒科*科：Function:showTree()Description:凹入显示二叉树Calls:voidInput:t:结点指针Return:voidOthers:NULL************************************************水voidshowTree(BT*t)〃显示二叉树voidshowTree(BT*t)〃显示二叉树BT*sta[100],*p;intlev[100][2];〃第一个空存要空的长度，第二空存摆布孩子的标示inttp,n,i,wid=4;if(t!=NULL)〃结点非空{printf(〃凹入法^去：\n〃)；tp=l；sta[tp]=t; 〃将各个结点的指针放在指针数组中lev[tp][O]=wid; 〃显示的前面的空白长度while(tp>0)(p=sta[tp];n=lev[tp][O];〃显示for(i=0;i<n;i++){printf(巧;printf("％c"，p->data);for(i=n+1;i<30;i+=2)(printf(“一”);}printf(H\nn);tp-；〃记录摆布孩子if(p->lchild!=NULL)(tp++；sta[tp]=p->lchild;lev[tp][O]=n+wid;lev[tp][1]=1;iif(p->rchild!=NULL)tp++；sta[tp]=p->rchild;lev[tp][O]=n+wid;lev[tp][1]=2;)}}本水本求水求水本水本本水本水求水本求水本水本水水求水求水本水水本水求水求水水求水本水本水水本水求水Function:preOrder()Description:先序遍历Calls:preOrder()Input:t:结点指针Return:voidQhers:NULL水本求水本水本水水本水本水本水水本水本水本水水本水本本本求水本水本水本水水本水本水本水水本水求水本voidpreOrder(BT*t)〃先序遍历if(t)〃结点不为空(printf(〃%3c〃,t->data);〃显示preOrder(t->lchild); //递归调用preOrder(t->rchild);}}***********它*******叱和叱***它它*****叱它叱*它它Function:postOrder()Description:后序遍历Calls:postOrder()Input:t:结点指针Return:voidQhers:NULL**来**求*求******来来*来*求*求**求*求本*水求水来水本求求*求水永水水水本水水求来voidpostOrder(BT*t)〃后序遍历if(t)〃结点不为空(postOrder(t->lchild);postOrder(t->rchild);printf(，z%3cz，,t->data);〃显示]*来****求*求***本水来本本*求本求水水水本水本水本水来本来本来本求水本水本水本水水来水本水Function:inOrder()Description:中序遍历Calls:inOrder()Input:t:结点指针Return:voidQhers:NULL*******************************求*水******求*****水*水voidinOrder(BT*t)〃中序遍历if(t)〃结点不为空{inOrder(t->lchild);printf(，z%3c，z,t->data);〃显示inOrder(t->rchild);1j*****来水来本****求水求*本水本水本水来*来本水本求水本水本水本水水本求本求本水来水水水水Function:levelOrder()Description:层次遍历Calls:voidInput:t:结点指针Return:voidQhers:NULL**来**求*求******来来*来*求*求**求*求本*水求水来水本求求*求水永水水水本水水本水voidlevelOrder(BT*t)〃层次遍历inti,j;BT*q[100];〃指针数组BT*p;P=t；if(p!=NULL)〃结点非空{i=l；q[i]=p;j=2；1while(i!=j)〃先将每一个结点的指针存入指针数组中，在显示出来p=q[0;printf("%3cH,p->data);if(p->lchild!=NULL)〃左孩子非空(qO]=p->lchild;j++;)if(p->rchild!=NULL)〃左孩子非空)qO]=p->rchild;j++；}i++；〃为了显示下一个结点}本家中本中中水中水中本中中水中水中本中中水中水中本中本水中水中本中本中中水中本中中水本水中本水本水Function:leafNum()Description:求二叉树叶子数Calls:leafNum()Input:t:结点指针Return:intQhers:NULL***********************************************水