数据结构_二叉树子系统设计

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

2、*lchild;/ 左孩子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);/* Function: main()Description: 主调函数Calls: createTree() showTree() preOrder

3、() postOrder() inOrder() leafNum() levelOrder() nodeNum() treeDepth()Input: NULLReturn: voidOthers: NULL* void main()BT *t = NULL;int choice, k = 1;while (k)printf("n二叉树子系统 n");printf("*n");printf("*1-建二叉树*n");printf("*2-凹入显示*n");printf("*3-先序遍历*n");

4、printf("*4-中序遍历*n");printf("*5-后序遍历*n");printf("*6-层次遍历*n");printf("*7-求叶子数*n");printf("*8-求结点数*n");printf("*9-求树深度*n");printf("*0- 返回*n");printf("*n");printf(" 请选择菜单号(0-9)：");fflush(stdin);scanf("%d"

5、, &choice);switch(choice)case 1:printf(" 请输入根结点( '0'表示该结点为空) ： "); t = createTree();printf(" 二叉树建立成功。 n");break;case 2:showTree(t); break;case 3:printf(" 先序遍历序列： "); if (t = NULL) printf(" 空。 n");elsepreOrder(t); break;case 4:printf(" 中序遍历序列：

6、"); if (t = NULL) printf(" 空。 n");elseinOrder(t); break;case 5:printf(" 后序遍历序列： "); if (t = NULL) printf(" 空。 n");elsepostOrder(t); break;case 6:printf(" 层次遍历序列： "); if (t = NULL) printf(" 空。 n");elselevelOrder(t); break;case 7:printf(" 该二叉

7、树的叶子数： "); if (t = NULL) printf("0 。 n"); elseprintf("%d。n", leafNum(t); break;case 8:printf(" 该二叉树的结点数为： "); if (t = NULL)printf("0 。 n"); elseprintf("%d 。 n", nodeNum(t); break;case 9:printf(" 该二叉树的深度为： "); if (t = NULL)printf("

8、0 。 n"); else printf("%d 。 n", treeDepth(t); break;case 0: k = 0; break;default:k = 1;break;/*Function: createTree()Description: 建立二叉树 Calls: createTree() Input: NULLReturn: BT *Others: NULL*/BT *createTree()/ 建立二叉树BT *t;char x;getchar();scanf("%c", &x); / 获取输入的结点值if (x

9、= '0') / 输入的值为零，结点为空t = NULL;elset = (BT *)malloc(sizeof(BT);t->data = x; / 赋值printf(" 请输入结点 %c 的左孩子： ", t->data); t->lchild = createTree(); / 递归建立左孩子 printf(" 请输入结点 %c 的右孩子： ", t->data); t->rchild = createTree(); / 递归调用return t;/*Function: showTree()Descri

10、ption: 凹入显示二叉树Calls: voidInput: t ：结点指针Return: voidOthers: NULL*/BT *sta100, *p;int lev1002; / 第一个空存要空的长度，第二空存左右孩子的标示 int tp, n, i, wid = 4;if (t != NULL) /结点非空printf(" 凹入表示法 :n");tp = 1;statp = t; / 将各个结点的指针放在指针数组中 levtp0 = wid; / 显示的前面的空白长度while (tp > 0)p = statp;n = levtp0;/ 显示for (i

11、 = 0; i< n; i+) printf(" ");printf("%c", p->data); for (i = n+1; i < 30; i+=2) printf(” ”)；printf("n")； tp-；/ 记录左右孩子 if (p->lchild != NULL) tp+；statp = p->lchild； levtp0 = n+wid； levtp1 = 1； if (p->rchild != NULL) tp+；statp = p->rchild； levtp0 = n+w

12、id；levtp1 = 2;*Function: preOrder() Description: 先序遍历 Calls: preOrder() Input: t ：结点指针 Return: voidOthers: NULL* void preOrder(BT *t) / 先序遍历if (t) / 结点不为空printf("%3c", t->data); / 显示 preOrder(t->lchild); / 递归调用 preOrder(t->rchild);/*Function: postOrder()Description: 后序遍历Calls: pos

13、tOrder()Input: t ：结点指针Return: voidOthers: NULL*/ void postOrder(BT *t) / 后序遍历if (t) / 结点不为空postOrder(t->lchild); postOrder(t->rchild); printf("%3c", t->data); / 显示*Function: inOrder()Description: 中序遍历Calls: inOrder()Input: t ：结点指针Return: voidOthers: NULL*/ void inOrder(BT *t) / 中序

14、遍历if (t) / 结点不为空 inOrder(t->lchild); printf("%3c", t->data); / 显示 inOrder(t->rchild);/*Function: levelOrder()Description: 层次遍历Calls: voidInput: t ：结点指针Return: voidOthers: NULL*/void levelOrder(BT *t) / 层次遍历int i, j;BT *q100; / 指针数组BT *p;p = t;if (p != NULL) / 结点非空i = 1;qi = p;j =

15、2;while (i != j) / 先将每个结点的指针存入指针数组中，在显示出来 p = qi;printf("%3c", p->data);if (p->lchild != NULL) / 左孩子非空qj = p->lchild;j+;if (p->rchild != NULL) / 左孩子非空qj = p->rchild;j+;i+; / 为了显示下一个结点/*Function: leafNum()Description: 求二叉树叶子数Calls: leafNum()Input: t ：结点指针Return: intOthers: NU

16、LL*/int leafNum(BT *t) / 叶子数int i = 0;if (t->lchild = NULL && t->rchild = NULL) / 左右孩子都为空 i+;elsei = leafNum(t->lchild) + i; / 递归访问左孩子的叶子数i = leafNum(t->rchild) + i;return i;/*Function: nodeNum() Description: 求二叉树结点数Calls: nodeNum()Input: t ：结点指针Return: intOthers: NULL */ int nodeNum(BT *t)/ 结点数int i = 0;if (t) / 结点不为空i+;i = nodeNum(t->lchild) + i;i = nodeNum(t->rchild) + i;return i; /* Function: treeDepth()Description: 求二叉树的深度Calls: treeDepth