《数据结构》课程设计报告
专业计算机科学与技术
班级3班
姓名
学号
指导教师
起止时间2012.12~2013.1
课程设计：二叉树
一、任务描述
二叉树的中序、前序、后序的递归、非递归遍历算法，应包含建树的实现。春天童话
任务：设计一个程序，实现二叉树的前序、中序、后序的递归遍历运算。
要求：
（1）创建二叉树；
（2）二叉树的前序、中序、后序的递归遍历运算实现。
二、问题分析
1、功能分析
分析设计课题的要求，要求编程实现以下功能：
（1）二叉树的建立—即创建二叉树；
ppt加视频
（2）二叉树的遍历—二叉树的前序、中序、后序操作；
2、数据对象分析
二叉树的遍历：包括前序、中序、后序
将二叉树补充到完全二叉树在输入，才能正确创建二叉树
三、数据结构设计
二叉树的建立和遍历的实现。有关的定义如下：
typedef int Status;
typedef char TElemType; //定义二叉树结点值的类型为字符型
struct BiTNode {//定义二叉树结点类型栈结点的类型
TElemType data; //数据域
BiTNode *lchild,*rchild;//指针域
};BiTNode *BiTree;
四、功能设计
（一）主控菜单设计
大蓟
程序运行后，输入提示，如下：“创建二叉树，请按前序序列输入各节点值：”
一粒扣子
正确输入二叉树后，提示“已成功创建二叉树”
（二）程序模块结构
由课题要求可将程序划分为以下几个模块（即实现程序功能所需的函数）：
●创建二叉树的函数void CreateBiTree(BiTree &T);
●二叉树的前序遍历函数Status PreOrderTraver(BiTree T,Status(*Visit)(TElemType));
●二叉树的中序遍历函数Status InOrderTraver(BiTree T,Status(*V isit)(TElemType));
●二叉树的后序遍历函数Status PostOrderTraver(BiTree T,Status(*Visit)(TElemType))；
●最简单的visit函数Status V isit(TElemType e);
（三）函数调用关系
其中main()是主函数，它进行菜单驱动。
BiTree T;
int n=0;
printf("创建二叉树，请按前序序列输入各节点值：\n");综采
CreateBiTree(T);
printf("\n");
printf("已成功创建二叉树\n");
PreOrderTraver( T,V isit);
printf("\n");
InOrderTraver(T,V isit);
printf("\n");
PostOrderTraver(T,V isit);
printf("\n");
（四）文件结构
1、tree.h：二叉树相关的定义与声明
2、tree.cpp：二叉树运算的实现
5、mn.cpp：主函数
（五）各函数的算法设计
1、CreateBiTree()
算法原理：按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，构造二叉链表
代码描述：void CreateBiTree(BiTree &T)
{char ch;
ch=getchar(); //读入一个字符
printf("%c",ch);
if (ch==' ') T=NULL;
el {if (!(T=(BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
//内存分配成功
T->data = ch; //生成根结点
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
士不可不弘毅
算法的时间复杂度分析：O(1)
2、PreOrderTraver ()
算法原理：若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树（3）先序遍历右子树
流程图：
流程图
代码描述：Status PreOrderTraver (BiTree T,Status (*visit)(TElemType e))
{ /*功能：先序遍历二叉树；参数:T为二叉树的根,visit为对结点的处理方法*/ if (T) { //若根结点不空
if(visit(T->data)) //访问根结点
if (PreOrderTraver(T->lchild,visit)) //先序遍历根的左子树
if(PreOrderTraver(T->rchild,visit)) //先序遍历根的右子树
return OK;
}
}
算法的时间复杂度分析：O(n)
3、InOrderTraver ()
电梯修理
算法原理：若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）
流程图：
代码描述：Status InOrderTraver (BiTree T,Status (*visit)(TElemType e)) {/*功能：中序遍历二叉树；参数:T为二叉树的根,visit为对结点的处理方法*/
if (T) { //若根结点不空
if (InOrderTraver(T->lchild,visit)) //中序遍历根结点的左子树
if(visit(T->data)) //访问根结点
if(InOrderTraver(T->rchild,visit)) //中序遍历根结点的右子树
return OK;
}
}
算法的时间复杂度分析：O(n)
4、PostOrderTraver()
算法原理：若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3
流程图：
代码描述：Status PostOrderTraver (BiTree T,Status (*visit)(TElemType e))
{/*功能：后序遍历二叉树；参数:T为二叉树的根,visit为对结点的处理方法*/
if (T) { //若根结点不空
if (PostOrderTraver(T->lchild,visit)) //后序遍历根结点的左子树
if(PostOrderTraver(T->rchild,visit)) //后序遍历根结点的右子树
if(visit(T->data)) //访问根结点
return OK;
}
平静的湖面像什么}
算法的时间复杂度分析：O(n)
五、测试数据和结果
1、测试数据
Abc de g f
2、测试结果
本程序在VC++环境下实现，下面是对以上测试数据的运行结果。
(1) 主菜单显示如下：
