《数据结构：二叉树子系统.docx》由会员分享，可在线阅读，更多相关《数据结构：二叉树子系统.docx（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、*题目：按屏幕提示用前序方法建立一棵二叉树，并能按凹入法显示二叉树结构。编写前序遍历、中序遍历、后序遍历、层次遍历程序。编写求二叉树的叶结点数、总结点数和深度的程序。设计一个选择式菜单，以菜单方式选择下列操作。二叉树子系统1 建二叉树2 凹入显示3 先序遍历4 中序遍历5 后序遍历6 层次遍历7 求叶子数8 求结点数9 求树深度10 返 回请选择菜单号(09)*/#include #include typedef struct bTree二叉树结点char data; 值域struct bTree *Ichild; 左孩子 struct bTree *rchild; 右孩子 BT;BT *cr
2、eateTree();void showTree(BT *t);void preOrder(BT *t);void postOrder(BT *t);void inOrder(BT *t);void levelOrder(BT*t);int leafNum(BT *t);int nodeNum(BT *t);int treeDepth(BT *t);Function: main()Description:主调函数Input: t:结点指针Return: intQhers: NULL*水*水*水*水*水*水水*水*水*水水*水水水水int nodeNum(BT*t)结点数inti=O;if (t
3、) 结点不为空(i+；i=nodeNum(t-lchild)4-i;i=nodeNum(t-rchild)+i;)return i;)*来*求*求*水来水*求*求*求*水米水来*来*求*求*本水水求水水水Function: treeDepth()Description:求二叉树的深度Calls: treeDepth()Input: t:结点指针Return: intQhers: NULL*来*求*求*来来*来*求*求*求*求本*水求水来水本求求*求水永水水水本水水求来int treeDepth(BT*t)二叉树的深度int Idep, rdep;if (t= NULL) 结点不为空 jretu
4、rn 0;)elseldep= treeDepth(t-lchild);rdep = treeDepth(t-rchild);if (ldeprdep) 左深度大于右深度 )return ldep+1; 返回左深度的值 return rdep+1;Calls: createTree() showTree() preOrder() postOrder() inOrder() leafNum() levelOrder() nodeNum() treeDepth()* *求*水*水*水*求水水水*水水*水Input: NULL Return: void Qhers: NULL *void main(
5、)(BT*t= NULL; int choice,k =1;while (k)printf（Hn二叉树子系统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表示该结点
6、为空)：);t =createTree();printf (二叉树建立成功。n)； break;showTree(t);break;printf(先序遍历序列：);if (t = NULL)printf (空。n)；elsepreOrder(t);)break;printf(中序遍历序列：);if (t = NULL)printf (空。n)；)else(inOrder(t);break;printf(后序遍历序列：);if (t = NULL)printf (空。n)；elsepostOrder(t);break;printf(层次遍历序列：);if (t = NULL)printf (空。
7、n)；levelOrder(t); break;printf (该二叉树的叶子数：)； if (t= NULL)( printf(O o n); else(printf(n%d 0 nn, leafNum(t);) break;printf(该二叉树的结点数为：)；if (t = NULL)( printf(O o n);else(printf(%d。n”,nodeNum(t);) break;printf (该二叉树的深度为：)；if (t = NULL)( printf(O o nH); elseprintf(%d。nM, treeDepth(t); break;case 0:k=0;br
8、eak;default:k=1;break;*来*永*来*永*永*永*永*水*水水水水水水水水求水水求水水水Function: createTree()Description:建立二叉树Calls: createTree()Input:NULLReturn: BT *Qhers: NULL*水*水* 求*水* 水* 永*求* 水*水水*水BT*createTree()建立二叉树BT*t;char x;getchar();scanf(%cn5&x); 获取输入的结点值if (x=0)输入的值为零，结点为空(t=NULL;)elset=(BT*)malloc(sizeof(BT);t-data =
9、x;赋值printf (请输入结点%c的左孩子：,t-data);t-lchild = createTree (); 递归建立左孩子 printf (请输入结点%c的右孩子：,t-data);t-rchild = createTree ();递归调用return t;)* 科*朴M*秒科* 科：Function: showTree()Description:凹入显示二叉树Calls: voidInput: t:结点指针Return: voidOthers: NULL*水void showTree(BT *t)显示二叉树BT*sta100,*p;int lev1002;第一个空存要空的长度，第二
10、空存摆布孩子的标示 int tp, n, i, wid =4;if (t !=NULL) 结点非空printf (凹入法去：n)；tp=l；statp=t;将各个结点的指针放在指针数组中levtp O=wid;显示的前面的空白长度while (tp0)(p=statp;n =levtpO;显示for(i=0;idata);for(i=n+1;ilchild != NULL)(tp+；statp= p-lchild;levtpO=n+wid;levtp1=1;iif (p-rchild != NULL)tp+；statp= p-rchild;levtpO= n+wid;levtp1=2;)本水本
11、求水求水本水本本水本水求水本求水本水本水水求水求水本水水本水求水求水水求水本水本水水本水求水Function: preOrder()Description:先序遍历Calls: preOrder()Input: t:结点指针Return: voidQhers: NULL水本求水本水本水水本水本水本水水本水本水本水水本水本本本求水本水本水本水水本水本水本水水本水求水本void preOrder(BT*t) 先序遍历if (t) 结点不为空(printf (%3c, t-data); 显示preOrder(t-lchild);/递归调用preOrder(t-rchild);*它* 叱和叱 *它它*
12、叱它叱*它它Function: postOrder()Description:后序遍历Calls: postOrder()Input: t:结点指针Return: voidQhers: NULL*来*求*求*来来*来*求*求*求*求本*水求水来水本求求*求水永水水水本水水求来void postOrder(BT*t) 后序遍历if (t) 结点不为空(postOrder(t-lchild);postOrder(t-rchild);printf (，z%3cz，, t-data);显示*来*求*求*本水来本本*求本求水水水本水本水本水来本来本来本求水本水本水本水水来水本水Function:inOr
13、der()Description:中序遍历Calls: inOrder()Input: t:结点指针Return: voidQhers: NULL*求*水*求*水*水void inOrder(BT*t) 中序遍历if (t) 结点不为空 inOrder(t-lchild);printf (，z%3c，z, t-data); 显示 inOrder(t-rchild);1j*来水来本*求水求*本水本水本水来*来本水本求水本水本水本水水本求本求本水来水水水水Function :levelOrder()Description:层次遍历Calls: voidInput: t:结点指针Return: vo
14、idQhers: NULL*来*求*求*来来*来*求*求*求*求本*水求水来水本求求*求水永水水水本水水本水void levelOrder (BT*t) 层次遍历int i,j;BT*q100; 指针数组 BT*p;P =t；if (p!=NULL) 结点非空 i=l；qi= p;j=2；1while(i!=j) 先将每一个结点的指针存入指针数组中，在显示出来p=q0;printf(%3cH, p-data);if (p-lchild !=NULL) 左孩子非空 (qO= p-lchild;j+;)if (p-rchild !=NULL) 左孩子非空 )qO= p-rchild;j+； i+；
15、 为了显示下一个结点 本家中本中中水中水中本中中水中水中本中中水中水中本中本水中水中本中本中中水中本中中水本水中本水本水Function: leafNum()Description:求二叉树叶子数Calls: leafNum()Input: t:结点指针Return: intQhers: NULL*水int leafNum(BT *t) 叶子数inti=O;if (t-lchild = NULL& t-rchild = NULL) 摆布孩子都为空 )i+；else (i=leafNum(t-lchild)+i;递归访问左孩子的叶子数 i=leafNum(t-rchild)+i;return i; 本求本本水本水本水本本水本水本水本本水本水求水水本水本水本水水家水本水本水水求水求水本水水本水本水Function: nodeNum()Description:求二叉树结点数Calls: nodeNum()