数据结构：二叉树子系统

*题目按屏幕提示用前序方法建立一棵二叉树，并能按凹入法显示二叉树结构编写前序遍历、中序遍历、后序遍历、层次遍历程序编写求二叉树的叶结点数、总结点数和深度的程序设计一个选择式菜单，以菜单方式选择下列操作二叉树子系统1建二叉树2凹入显示3先序遍历4中序遍历5后序遍历6层次遍历7求叶子数8求结点数9求树深度10--------返回请选择菜单号0—9*/#include stdio.h#include stdlib.h〃二叉树结点typedef struct bTreechar data;〃值域struct bTree*Ichild;〃左孩子structbTree*rchild;〃右孩子}BT;BT*createTree;void showTreeBT*t;void preOrderBT*t;void postOrderBT*t;void inOrderBT*t;void levelOrderBT*t;int leafNumBT*t;int nodeNumBT*t;int treeDepthBT*t;Function:mainDescription:主调函数Input:t:结点指针Return:intQhers:NULL**♦♦********水*********水*水****水*水*水水*水*水*水水*水水水水〃结点数int nodeNumBT*tinti=O;if t〃结点不为空；i++i=nodeNumt-lchild4-i;i=nodeNumt-rchild+i;return i;*来****求*求****水来水**求*求*求****水米水来*来*求*求*****本水水求水水水Function:treeDepthDescription:求二叉树的深度Calls:treeDepthInput:t:结点指针Return:intQhers:NULL**来**求*求******来来*来*求*求**求*求本*水求水来水本求求*求水永水水水本水水求来〃二叉树的深度int treeDepthBT*tint Idep,rdep;if t=NULL〃结点不为空jreturn0;else[ldep=treeDeptht-lchild;rdep=treeDeptht-rchild;〃左深度大于右深度if ldeprdepreturnldep+1;〃返回左深度的值return rdep+1;Calls:createTree showTreepreOrder postOrderinOrder leafNumlevelOrdernodeNum treeDepthInput:NULL Return:void Qhers:NULL********************void main**求*水*水**水*求水水水*水水*水BT*t=NULL;int choice,k=1;while kprintf（H\n二叉树子系统\n〃）；printf〃请选择菜单号*******************************printf0-9:〃;1——建一叉树printsfflushstdin;凹入显示*2—printf％scanfd”,choice;printfn3—-----先序遍历4—中序遍历printf-switchchoiceprintfC,5—后序遍历6———层次遍printff,历printf〃请输入根结printfM7—求叶子数点O表示该结点为8————求结点printf*空〃;数9————求树深printf*t=createTree;度一返回printf-0-printf〃二printf jMcfaK***************************1叉树建立成功n）\n〃；break;showTreet;break;printf〃先序遍历序列〃;if t==NULL{printf〃空\n〃；else{preOrdert;break;printf〃中序遍历序列〃;if t==NULLprintf〃空\n〃；elseinOrdert;}break;printf〃后序遍历序列〃;if t==NULL{printf〃空\n〃；}else{postOrdert;}break;printf〃层次遍历序列〃;if t==NULLprintf〃空\n〃；}levelOrdert;break;}printf〃该二叉树的叶子数〃；if t==NULL printfO\n;oelse}n nprintf%d\n,leafNumt;0break;printf〃该二叉树的结点数为〃；if t==NULL printfO\n;oelseprintf%d\n”,nodeNumt;break;printf〃该二叉树的深度为〃；if t==NULLH printfO\n;oelse}Mprintf%d\n,treeDeptht;break;}case0:k=0;break;default:k=1;break;********来****永*来****永*永****永*永**水*水水水水水水水水求水水求水水水Function:createTreeDescription:建立二叉树Calls:createTreeInput:NULLReturn:BT*Qhers:NULL**********************水*水****求*水*水**永*求*水**水水*水〃建立二叉树BT*createTreeBT*t;char x;getchar;n〃获取输入的结点值scanf%c x;5if x=0‘〃输入的值为零，结点为空t=NULL;else{t=BT*mallocsizeofBT;t-data=x;〃赋值printf〃请输入结点%c的左孩子〃,t-data;t-lchild=createTree;〃递归建立左孩子printf〃请输入结点%c的右孩子〃,t-data;t-rchild=createTree;〃递归调用}return t;**********************科***朴M*******秒科*科Function:showTreeDescription:凹入显示二叉树Calls:voidInput:t:结点指针Return:voidOthers:NULL************************************************水〃显示二叉树void showTreeBT*tBT*sta

[100],*p;int lev

[100]

[2];〃第一个空存要空的长度，第二空存摆布孩子的标示int tp,n,i,wid=4;if t!=NULL〃结点非空{printf〃凹入法^去\n〃；；tp=lsta[tp]=t;〃将各个结点的指针放在指针数组中lev[tp][O]=wid;〃显示的前面的空白长度while tp0p=sta[tp];n=lev[tp][O];〃显示fori=0;in;i++{巧;printf％，printf cp-data;fori=n+1;i30;i+=2一”;printf“}H nprintf\n;；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:preOrderDescription:先序遍历Calls:preOrderInput:t:结点指针Return:voidQhers:NULL水本求水本水本水水本水本水本水水本水本水本水水本水本本本求水本水本水本水水本水本水本水水本水求水本〃先序遍历void preOrderBT*tif t〃结点不为空printf〃%3c〃,t-data;〃显示//递归调用preOrdert-lchild;preOrdert-rchild;}}***********它*******叱和叱***它它*****叱它叱*它它Function:postOrderDescription:后序遍历Calls:postOrderInput:t:结点指针Return:voidQhers:NULL**来**求*求******来来*来*求*求**求*求本*水求水来水本求求*求水永水水水本水水求来〃后序遍历void postOrderBT*tif t〃结点不为空postOrdert-lchild;postOrdert-rchild;printf，z%3cz，,t-data;〃显示]*来****求*求***本水来本本*求本求水水水本水本水本水来本来本来本求水本水本水本水水来水本水Function:inOrderDescription:中序遍历Calls:inOrderInput:t:结点指针Return:voidQhers:NULL*******************************求*水******求*****水*水〃中序遍历void inOrderBT*tif t〃结点不为空{inOrdert-lchild;printf，z%3c，z,t-data;〃显示inOrdert-rchild;1J*****来水来本****求水求*本水本水本水来*来本水本求水本水本水本水水本求本求本水来水水水水Function:levelOrderDescription:层次遍历Calls:voidInput:t:结点指针Return:voidQhers:NULL**来**求*求******来来*来*求*求**求*求本*水求水来水本求求*求水永水水水本水水本水void levelOrderBT*t〃层次遍历int i,j;BT*q

[100];〃指针数组BT*p;；P=tif p!=NULL〃结点非空{i=l；q[i]=p;j=2；1whilei!=j〃先将每一个结点的指针存入指针数组中，在显示出来p=q[0;Hprintf%3c,p-data;if p-lchild!=NULL〃左孩子非空qO]=p-lchild;j++;if p-rchild!=NULL〃左孩子非空qO]=p-rchild;；j++}；〃为了显示下一个结点i++}本家中本中中水中水中本中中水中水中本中中水中水中本中本水中水中本中本中中水中本中中水本水中本水本水Function:leafNumDescription:求二叉树叶子数Calls:leafNumInput:t:结点指针Return:intQhers:NULL***********************************************水〃叶子数int leafNumBT*tinti=O;if t-lchild=NULL t-rchild=NULL〃摆布孩子都为空；i++}elsei=leafNumt-lchild+i;〃递归访问左孩子的叶子数i=leafNumt-rchild+i;}return i;■本求本本水本水本水本本水本水本水本本水本水求水水本水本水本水水家水本水本水水求水求水本水水本水本水Function:nodeNumDescription:求二叉树结点数Calls:nodeNum。