数据结构：二叉树子系统(11页).doc

《数据结构：二叉树子系统(11页).doc》由会员分享，可在线阅读，更多相关《数据结构：二叉树子系统(11页).doc（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、data; /值域 struct bTree *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: createTre

3、e() showTree() preOrder() 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); printf(* 4-中序遍历 *n); p

4、rintf(* 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, &choice); switch(choice) case 1: printf(请输入根结点（0表示该结点为空）：); t = createTree(); printf(二叉树建立成功。n); break; case 2: showT

5、ree(t); break; case 3: printf(先序遍历序列：); if (t = NULL) printf(空。n); else preOrder(t); break; case 4: printf(中序遍历序列：); if (t = NULL) printf(空。n); else inOrder(t); break; case 5: printf(后序遍历序列：); if (t = NULL) printf(空。n); else postOrder(t); break; case 6: printf(层次遍历序列：); if (t = NULL) printf(空。n); el

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

7、 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 = 0) /输入的值为零，结点为空 t = NULL; else t = (BT *)malloc(sizeof(BT); t-data = x; /

8、赋值 printf(请输入结点%c的左孩子：, t-data); t-lchild = createTree(); /递归建立左孩子 printf(请输入结点%c的右孩子：, t-data); t-rchild = createTree(); /递归调用 return t;/*Function: showTree()Description: 凹入显示二叉树Calls: voidInput: t：结点指针Return: voidOthers: NULL*/void showTree(BT *t) /显示二叉树 BT *sta100, *p; int lev1002; /第一个空存要空的长度，第二

9、空存左右孩子的标示 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 = 0; idata); for (i = n+1; i lchild != NULL) tp+; statp = p-lchild; levtp0 = n+wid; levtp1 = 1; if (p-rchild != NULL) tp

10、+; statp = p-rchild; levtp0 = n+wid; 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: 后序遍历Call

11、s: postOrder()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) /中序遍历 if (t) /结点不为空 inOrd

12、er(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 = 2; while (i != j) /先将每个结点的指针存入指针数组中，在显示出来

13、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: NULL*/int leafNum(BT *t) /叶子数 int i = 0; if (t-lchild = NULL & t-rchild

14、 = NULL) /左右孩子都为空 i+; else i = 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)

15、+ i; return i;/*Function: treeDepth()Description: 求二叉树的深度Calls: treeDepth()Input: t：结点指针Return: intOthers: NULL*/int treeDepth(BT *t) /二叉树的深度 int ldep, rdep; if (t = NULL) /结点不为空 return 0; else ldep = treeDepth(t-lchild); rdep = treeDepth(t-rchild); if (ldep rdep) /左深度大于右深度 return ldep+1; /返回左深度的值 else return rdep+1; -第 11 页-