重庆大学城市科技学院
课程设计报告
二叉树的基本操作
学院：电气信息学院
专业：软件工程
年级： 2011 姓名：
班级： 01 学号： 20110286 成绩：
完成时间： 2013年1月2日
指导教师：
目录
一、需求分析 (3)
二、概要设计 (3)
三、详细设计 (4)
zhiwei
四、调试结果 (11)
五、课程设计总结 (11)
芒果榨汁
一、需求分析
二叉树形象地说即树中每个节点最多只有两个分支，它是一种重要的数据类型。可以运用于建立家谱，公司所有的员工的职位图，以及各种事物的分类和各种机构的职位图表等。
二叉树是通过建立一个链式存储结构，达到能够实现前序遍历，中序遍历，后序遍历。以及能够从输入的数据中得知二叉树的叶子结点的个数，二叉树的深度。在此，二叉树的每一个结点中必须包括：
值域，左指针域，右指针域。演示程序以用户与计算机对话的方式进行，即在计算机终端上显示提示信息后，由用户在键盘上输入相应动作的序号和相应的输入数据。
1.1课程设计任务及要求
房屋过户流程(1)按先序次序输入二叉树中结点的值，构造二叉链表表示的二叉树t；
(2)对二叉树t作先序、中序、后序遍历的递归算法，输出结果；
(3)计算二叉树t的深度，输出结果；
(4)计算二叉树t的叶子结点个数
1.2课程设计思想
本次课程设计中，用到的主要知识就是递归思想，着重体会递归的思想。建立二叉树采用先序次序插入的方式。对二叉树进行遍历时采用递归函数的方式。求二叉树的深度及叶子结点个数均采用递归方式。
二、概要设计
2.1对程序中定义的核心数据结构及对其说明：
typedef struct BiTNode双语小学
{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
在开头定义了二叉树的链式存储结构，此处采用了每个结点中设置三个域，即值域，左指针域和右指针域。
2.2 程序模块及其功能：
本程序分为：7大模块。二叉树的建立链式存储结构、前序遍历、中序遍历、后序遍历、求叶子结点的个数计算、中序遍历、后序遍历、深度、主函数。
1、二叉树的建立链式存储结构；首先typedef struct BiTNode：定义二叉树的链式存储结构，此处采
用了每个结点中设置三个域，data：即值域，*lchild：左指针域和rchild：右指针域。
2、二叉树的前序遍历；利用二叉链表作为存储结构的前序遍历：先访问根结点，再依次访问左右子树。
3、二叉树的中序遍历；利用二叉链表作为存储结构的中序遍历：先访问左子数，再访问根结点，最后访问右子树。
4、二叉树的后序遍历；利用二叉链表作为存储结构的前序遍历：先访问左右子树，再访问根结点。
5、求二叉树的深度：首先判断二叉树是否为空，若为空则此二叉树的深度为0。否则，就先别求出左右子树的深度并进行比较，取较大的+1就为二叉树的深度。
6、二叉树的求叶子结点的个数计算；先分别求得左右子树中各叶子结点个数，再计算出两者之和即为二叉树的叶子结点数。
7、主函数。主函数中分别调用各函数。
三、详细设计
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;
el
{
if(!(t=(bitnode *)malloc(sizeof(bitnode)))) exit(overflow);
t->data=ch;
t->lchild=createbitree(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->lchild);
t->rchild=createbitree(t->rchild);
将二叉树中的每一个结点设置为：值域，左指针域，右指针。
形容美食的诗句
台风菲特这一小段程序实现了二叉树的置空，二叉树的建立，二叉树的存储。
下凡尘
3.2前序遍历：先访问根结点，再访问左子树，最后访问右子树。
具体函数为：
void preordertraver(bitree t)
{
if(t)
{
printf("%c",t->data);
preordertraver(t->lchild);
preordertraver(t->rchild);
}
}
