数据结构课程设计(二叉树的基本操作)

1、精选优质文档-倾情为你奉上重庆大学城市科技学院课程设计报告 二叉树的基本操作 学 院： 电气信息学院 专 业： 软件工程 年 级： 2011 姓 名： 班 级： 01 学 号： 成 绩： 完成时间： 2013年1月2日 指导教师： 目录11一、需求分析二叉树形象地说即树中每个节点最多只有两个分支，它是一种重要的数据类型。可以运用于建立家谱，公司所有的员工的职位图，以及各种事物的分类和各种机构的职位图表等。二叉树是通过建立一个链式存储结构，达到能够实现前序遍历，中序遍历，后序遍历。以及能够从输入的数据中得知二叉树的叶子结点的个数，二叉树的深度。在此，二叉树的每一个结点中必须包括：值域，左指针域，

2、右指针域。演示程序以用户与计算机对话的方式进行，即在计算机终端上显示提示信息后，由用户在键盘上输入相应动作的序号和相应的输入数据。1.1课程设计任务及要求(1)按先序次序输入二叉树中结点的值,构造二叉链表表示的二叉树t；(2)对二叉树t作先序、中序、后序遍历的递归算法,输出结果；(3)计算二叉树t的深度,输出结果；(4)计算二叉树t的叶子结点个数1.2课程设计思想本次课程设计中，用到的主要知识就是递归思想，着重体会递归的思想。建立二叉树采用先序次序插入的方式。对二叉树进行遍历时采用递归函数的方式。求二叉树的深度及叶子结点个数均采用递归方式。 二、概要设计2.1对程序中定义的核心数据结构及对其说

3、明：typedef struct BiTNode char data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;在开头定义了二叉树的链式存储结构，此处采用了每个结点中设置三个域， 即值域，左指针域和右指针域。2.2 程序模块及其功能：本程序分为：7大模块。二叉树的建立链式存储结构、前序遍历、中序遍历、后序遍历、求叶子结点的个数计算、中序遍历、后序遍历、深度、主函数。1、二叉树的建立链式存储结构；首先typedef struct BiTNode：定义二叉树的链式存储结构，此处采用了每个结点中设置三个域，data：即值域，*lchild：左指针

4、域和rchild：右指针域。2、二叉树的前序遍历；利用二叉链表作为存储结构的前序遍历：先访问根结点，再依次访问左右子树。3、二叉树的中序遍历；利用二叉链表作为存储结构的中序遍历：先访问左子数，再访问根结点，最后访问右子树。4、二叉树的后序遍历；利用二叉链表作为存储结构的前序遍历：先访问左右子树，再访问根结点。5、求二叉树的深度：首先判断二叉树是否为空，若为空则此二叉树的深度为0。否则，就先别求出左右子树的深度并进行比较，取较大的+1就为二叉树的深度。6、二叉树的求叶子结点的个数计算；先分别求得左右子树中各叶子结点个数，再计算出两者之和即为二叉树的叶子结点数。7、主函数。主函数中分别调用各函数。

5、三、详细设计3.1存储结构的建立由递归函数实现具体函数为：typedef struct bitnode telemtype data; struct bitnode *lchild,*rchild;bitnode ,*bitree;bitree createbitree(bitree t)char ch;scanf("%c",&ch);if(ch='#') t=NULL;elseif(!(t=(bitnode *)malloc(sizeof(bitnode) exit(overflow);t->data=ch;t->lchild=crea

6、tebitree(t->lchild);t->rchild=createbitree(t->rchild);return t;在创建的二叉树中，左右孩子都为字符型。char的作用是输入n个任意的字符，而且在输入n个字符后，必须输入n+1个'0'，才能得到本程序所有能够实现的功能。t=Null是将二叉树置空。if(!(t=(bitnode *)malloc(sizeof(bitnode)，采用动态申请新结点的方式，不仅实现起来方便，而且还节省大量的存储空间。t->data=ch;值域t->lchild=createbitree(t->lchil

7、d);t->rchild=createbitree(t->rchild);将二叉树中的每一个结点设置为：值域，左指针域，右指针。这一小段程序实现了二叉树的置空，二叉树的建立，二叉树的存储。3.2前序遍历：先访问根结点，再访问左子树，最后访问右子树。具体函数为：void preordertraverse(bitree t)if(t)printf("%c",t->data);preordertraverse(t->lchild);preordertraverse(t->rchild);3.3中序遍历：先访问左子树，再访问根结点，最后访问右子树。具体

8、函数为：void inordertraverse(bitree t) if (t) inordertraverse(t->lchild);printf("%c",t->data);inordertraverse(t->rchild); 3.4后序遍历：先访问左子树，再访问右子树，最后访问根结点。具体函数为：void postordertraverse(bitree t) if(t)postordertraverse(t->lchild);postordertraverse(t->rchild);printf("%c",t-&

9、gt;data); 3.5求二叉树的深度：先定义三个整形变量m,n.如果树为空，则height=0；否则，先分别访问出左右子树的深度，再进行比较，将较大的+1的结果就是所求二叉树的深度。具体函数为：int height(bitree t)int m,n;if(t=NULL) return 0;else m=height(t->lchild);n=height(t->rchild);return (m>n)?m+1:n+1;3.6求叶子结点的个数：用leafcount变量表示叶子结点的总个数，用leafcount(t->lchild)、leafcount(t->rc

10、hild)分别表示访问的左右子树中叶子结点的个数。当树为空时讨论叶子结点个数无意义；当树非空时分为：一、左右子数都不存在时，即叶子结点的个数为1；二、左右子树存在，就用分别访问出左右子树中叶子结点的个数，两者相加就为二叉树叶子结点的个数。具体函数为：int leafcount(bitree t) if(!t) return 0; /空数无叶子 else if(!t->lchild&&!t->rchild) return 1; else return leafcount(t->lchild)+leafcount(t->rchild);3.7主函数：包括：二

11、叉树的数据结构bitree t、函数createbitree、height、leafcount、前序遍历preordertraverse、中序遍历inordertraverse、后序遍历postordertraverse。具体函数为：void main()bitree t;int w,v;printf("请输入建树字符序列:");t=createbitree(t);printf("先序遍历的结果是:");preordertraverse(t);printf("n");printf("中序遍历的结果是:");inor

12、dertraverse(t);printf("n");printf("后序遍历的结果是:");postordertraverse(t);printf("n");printf("二叉树的深度是:");w=height(t);printf("%dn",w);printf("二叉树的叶子结点的数目为:");v=leafcount(t);printf("%d",v);printf("n");3.8完整代码：#include <stdio.

13、h>#include <malloc.h>#include <process.h>#define ok 1#define error 0#define overflow -1typedef char telemtype;typedef struct bitnode /存储结构的建立 telemtype data; struct bitnode *lchild,*rchild;bitnode ,*bitree;bitree createbitree(bitree t)char ch;scanf("%c",&ch);if(ch='0

14、') t=NULL; /t=NULL是将二叉树置空elseif(!(t=(bitnode *)malloc(sizeof(bitnode) exit(overflow); /动态申请新结点t->data=ch; /值域t->lchild=createbitree(t->lchild); /左指针域t->rchild=createbitree(t->rchild); /右指针域return t; /先序遍历void preordertraverse(bitree t) if(t)printf("%c",t->data);preord

15、ertraverse(t->lchild);preordertraverse(t->rchild); /中序遍历void inordertraverse(bitree t)if (t) inordertraverse(t->lchild);printf("%c",t->data);inordertraverse(t->rchild); /后序遍历 void postordertraverse(bitree t) if(t)postordertraverse(t->lchild);postordertraverse(t->rchild

16、);printf("%c",t->data); /判断深度 int height(bitree t)int m,n;if(t=NULL) return 0;else m=height(t->lchild);n=height(t->rchild);return (m>n)?m+1:n+1; /叶子结点个数int leafcount(bitree t) /leafcount表示叶子结点的总个数if(!t) return 0; /空数无叶子else if(!t->lchild&&!t->rchild) return 1;else

17、 return leafcount(t->lchild)+leafcount(t->rchild); void main()bitree t;int w,v;printf("请输入建树字符序列，以0表示NULL:");t=createbitree(t);printf("先序遍历的结果是:");preordertraverse(t);printf("n");printf("中序遍历的结果是:");inordertraverse(t);printf("n");printf("后

18、序遍历的结果是:");postordertraverse(t);printf("n");printf("二叉树的深度是:");w=height(t);printf("%dn",w);printf("二叉树的叶子结点的数目为:");v=leafcount(t);printf("%d",v);printf("n"); 四、测试结果五、课程设计总结-本程序基本上实现了前序遍历，中序遍历，后序遍历，叶子结点个数的求出，二叉树深度的求出等基本操作。 迈着时间的步伐，这次的课程设计也即将结束，但这个学期数据结构的学习还是具有相当大的意义，特别是这次的课程设计,它从一个程度上改变了我的编程思想，如何将一个程序快速而又准备的进行编写，进行编译，都成为了我思考的重点。同时通过这一个学期的学习，我们将数据结构的思想带入到了我们以后的编程学习中去。在这个阶段，我也明白了，好的思想，不