数据结构二叉树子系统

1、/题目：按屏幕提示用前序方法建立一棵二叉树，并能按凹入法显示二 叉树结构。W编写前序遍历、中序遍历、后序遍历、层次遍历程序。* 编写求二叉树的叶结点数、总结点数和深度的程序。* 设计一个选择式菜单，以菜单方式选择下列操作。* 二叉树子系统* * *1-建二叉树* *2-凹入显示*3-先序遍历* *4-中序遍历* *5-后序遍历* *6-层次遍历* *7-求叶子数* *8-求结点数* *9-求树深度* *0-返回* *请选择菜单号(0-9)7include <stdio.h>include <stdlib.h>typedef struct bTree / 二叉树结点cha

2、r data; / 值域struct bTree Jchild;/ 左孩子struct bTree *rchild;/ 右孩子BT;BT *createTree();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);严十w十w"十十 Function: main()Description:主调函数Calls

3、: createTree() showTree() preOrder() postOrder() in Order()leafNum() levelOrder() no deNum() treeDepth()In put: NULLReturn: voidOthers: NULL void mai n()BT *t = NULL;int choice, k = 1;while (k)prin tf(H*1- 建二叉树呵);prin tf(H*2 凹入显示5");prin tf(H*3- -先序遍历prin tf(H*4 中序遍历prin tf(H*5- 后序遍历5");pr

4、in tf(H*6 层次遍历呵);prin tf(H*7- 求叶子数呵);prin tf(H*8- 求结点数呵);prin tf(H*9- 求树深度5");prin tf(H*0 返回呵);printfC'n二叉树子系统n”);prin tf("*«*«*nH)prin tf("rf)print"请选择菜单号(09): H);fflush(stdi n); scan f(M%dM, &switch(choice)case 1:printf("请输入根结点('O'表示该结点为空):”); t =

5、 createTree();printfC二叉树建立成功o nM);break;case 2: showTree(t); break;case 3:prints先序遍历序列:M); if (t = NULL)printf(”空。np);elsepreOrder(t); break;case 4:printf(冲序遍历序列：”)；if (t = NULL) printf"空。np);elsein Order(t); break;case 5:printfC后序遍历序列：J； if (t = NULL) printf(H空。np);else postOrder(t); break;cas

6、e 6:printf(”层次遍历序列：J; if (t = NULL)printf"空。nM); elselevelOrder(t); break;case 7:printf(”该二叉树的叶子数;if (t = NULL)printf(H0o nH);elseprintf(”d。n' leafNum(t); break;case 8:printfC该二叉树的结点数为：")；if (t = NULL)printf(H0o nH);elseprintf(H%d。rT, nodeNum(t); break;case 9:printfC该二叉树的深度为:H)；if(t= N

7、ULL) printf("Oo nM);elseprintf(H%do n". treeDepth(t); break;case 0:k = 0; break;default:k= 1;break;Function: createTree()Description健立二叉树Calls: createTree()In put: NULLReturn: BT *Others: NULLBT *createTree()/ 建立二叉树BT t;char x;getchar();scan f("%c", &x); 获取输入的结点值if (x :O)输入的值

8、为零，结点为空t =NULL;elset = (BT *)malloc(sizeof(BT);t->data = x; / 赋值printf(”请输入结点 %c 的左孩子t->data); t->lchild = createTree(); /递归建立左孩子printf("请输入结点%c 的右孩子:", t->data); t->rchild = createTreeQ; /递归调用 return t;Function: showTree()Description:凹入显示二叉树Calls: voidIn put: t ：结点指针Return:

9、 voidOthers: NULLvoid showTree(BT *t)/ 显示二叉树BT *sta100, *p;int lev1002; 第一个空存要空的长度，第二空存左右孩子的标示 int tp, n, i, wid = 4;if (t !=NULL) 结点非空printtf凹入表示法:n“)；tp = 1;statp = t; /将各个结点的指针放在指针数组中levtpO =wid; 显示的前面的空白长度while (tp > 0)p = statp;n = levtpO;显示for (i = 0; i< n; i+)printf(,m);printf(M%c,'

10、, p->data);for (i = n+1; i < 30; i+=2) printf(” ");prin tf(,nH);tp-；记录左右孩子if (p->lchild != NULL)tp+； statp = p->lchild; levtpO = n+wid; levtp1 =1;if (p->rchild != NULL)tp+;statp = p->rchild;levtpO = n+wid;欢迎下载10Function: preOrder() Description:先序遍历 Calls: preOrder() In put: t

11、：结点指针 Return: voidOthers: NULLvoid preOrder(BT *t)/ 先序遍历if (t) 结点不为空printf(”3c”, t->data); / 显示 preOrder(t->lchild); / 递归 调用 preOrder(t->rchild);Function: postOrder()Description:后序遍历Calls: postOrder()In put: t :结点指针Return: voidOthers: NULLvoid postOrder(BT *t)/ 后序遍历if (t) 结点不为空postOrder(t-&

12、gt;lchild); postOrder(t->rchild); printf(H%3c,', t>data); / ® 7jFunction: in Order() Description:中序遍历 Calls: in Order() In put: t ：结点指针 Return: voidOthers: NULLvoid inOrder(BT #t)/ 中序遍历if (t) 结点不为空in Order(t->lchild);printf(M%3cH, t->data); / 显示in Order(t->rchild);/Function:

13、levelOrder()Description:层次遍历Calls: voidIn put: t ：结点指针Return: voidOthers: NULLvoid levelOrder(BT *t)/ 层次遍历int i. j；BT WOO;/指针数组BT wp；P = t；if(p != NULL) / 结点非空i = 1;qi = p;j = 2；while (i != j) /先将每个结点的指针存入指针数组中，在显示出来p = q【i；prin tf(,%3c',l p->data);if (p->lchild != NULL)/ 左孩子非空qO = p->l

14、child;j+;if (p->rchild != NULL) / 左孩子非空qO) = p->rchild;j+；i+；/为了显示下一个结点/Function: leafNum()Description:求二叉树叶子数Calls: leafNum()In put: t :结点指针Return: intOthers: NULLint leafNum(BT *t)/ 叶子数int i = 0;if (t->lchild = NULL && t->rchild = NULL) / 左右孩子都为空 i+；elsei = leafNum(t->lchild

15、) + i; 递归访问左孩子的叶子数i = leafNum(t->rchild) + i;return i;/Function: no deNum()Description:求二叉树结点数Calls: nodeNumQIn put: t ：结点指针Return: intOthers: NULLint nodeNum(BT *t)/结点数int i = 0;if (t) 结点不为空i+；i = no deNum(t->lchild) + i;i = no deNum(t->rchild) + i;return i;/Function: treeDepth()Description:求二叉树的深度Calls: treeDepth()In put: