二叉树实验报告.doc

《数据结构》
课程设计报告

专 业 计算机科学与技术
班 级 3班
姓 名
学 号
指导教师
起止时间 2012.12~2013.1

课程设计：二叉树
一、任务描述
二叉树的中序、前序、后序的递归、非递归遍历算法，应包含建树的实现。
任务：设计一个程序，实现二叉树的前序、中序、后序的递归遍历运算。
要求：
（1）创建二叉树；
（2）二叉树的前序、中序、后序的递归遍历运算实现。
二、问题分析
1、功能分析
分析设计课题的要求，要求编程实现以下功能：
（1） 二叉树的建立—即创建二叉树；
（2） 二叉树的遍历—二叉树的前序、中序、后序操作；
2、数据对象分析
二叉树的遍历：包括前序、中序、后序
将二叉树补充到完全二叉树在输入，才能正确创建二叉树
三、数据结构设计
二叉树的建立和遍历的实现。有关的定义如下：
typedef int Status;
typedef char TElemType; //定义二叉树结点值的类型为字符型
struct BiTNode {//定义二叉树结点类型栈结点的类型
TElemType data; //数据域
BiTNode *lchild,*rchild;//指针域
};BiTNode *BiTree;
四、功能设计
（一）主控菜单设计
程序运行后，输入提示，如下：“创建二叉树，请按前序序列输入各节点值：”
正确输入二叉树后，提示“已成功创建二叉树”
（二）程序模块结构
由课题要求可将程序划分为以下几个模块（即实现程序功能所需的函数）：
l 创建二叉树的函数void CreateBiTree(BiTree &T);
l 二叉树的前序遍历函数 Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType));
l 二叉树的中序遍历函数Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType));
l 二叉树的后序遍历函数Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType))；
l 最简单的visit函数Status Visit(TElemType e);
（三）函数调用关系
程序的主要结构（函数调用关系）如下图所示。
Main() Visit()

CreateBiTree() PreOrderTraverse() InOrderTraverse() PostOrderTraverse()
其中main()是主函数，它进行菜单驱动。
BiTree T;
int n=0;
printf("创建二叉树，请按前序序列输入各节点值：\n");
CreateBiTree(T);
printf("\n");
printf("已成功创建二叉树\n");
PreOrderTraverse( T,Visit);
printf("\n");
InOrderTraverse(T,Visit);
printf("\n");
PostOrderTraverse(T,Visit);
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;
else {if (!(T=(BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
//内存分配成功
T->data = ch; //生成根结点
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
算法的时间复杂度分析：O(1)
2、PreOrderTraverse ()
算法原理：若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树（3）先序遍历右子树
流程图：

流程图 存在一个二叉树

是否为空树

访问根结点 退出程序

先序遍历左子树

先序遍历右子树

代码描述：Status PreOrderTraverse (BiTree T,Status (*visit)(TElemType e))
{ /*功能:先序遍历二叉树;参数:T为二叉树的根,visit为对结点的处理方法*/
if (T) { //若根结点不空
if(visit(T->data)) //访问根结点
if (PreOrderTraverse(T->lchild,visit)) //先序遍历根的左子树
if(PreOrderTraverse(T->rchild,visit)) //先序遍历根的右子树
return OK;
}
}
算法的时间复杂度分析：O(n)
3、InOrderTraverse ()
算法原理：若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树；
流程图： 存在一个二叉树

是否为空树

中序遍历左子树 退出程序

访问根节点

中序遍历右子树

代码描述：Status InOrderTraverse (BiTree T,Status (*visit)(TElemType e)) {/*功能:中序遍历二叉树;参数:T为二叉树的根,visit为对结点的处理方法*/
if (T) { //若根结点不空
if (InOrderTraverse(T->lchild,visit)) //中序遍历根结点的左子树
if(visit(T->data)) //访问根结点
if(InOrderTraverse(T->rchild,visit)) //中序遍历根结点的右子树
return OK;
}
}
算法的时间复杂度分析：O(n)
4、PostOrderTraverse()
算法原理：若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点
流程图： 存在一个二叉树

是否为空树

后序遍历左子树 退出程序

后序遍历右子树

访问根节点

代码描述：Status PostOrderTraverse (BiTree T,Status (*visit)(TElemType e))
{/*功能:后序遍历二叉树;参数:T为二叉树的根,visit为对结点的处理方法*/
if (T) { //若根结点不空
if (PostOrderTraverse(T->lchild,visit)) //后序遍历根结点的左子树
if(PostOrderTraverse(T->rchild,visit)) //后序遍历根结点的右子树
if(visit(T->data)) //访问根结点
return OK;
}
}
算法的时间复杂度分析：O(n)
五、测试数据和结果
1、测试数据
Abc de g f
2、测试结果
本程序在VC++环境下实现，下面是对以上测试数据的运行结果。
(1) 主菜单显示如下：

(2) 建立二叉树及各种遍历：

六、结束语
本设计完成了课题要求的任务，较熟练地建立了二叉树，实现了各种遍历算法设计了较便捷的操作界面。
这可让他犯了难，施工现场距离项目部很远，没有车还真是不方便office, branch offices (jurisdiction), risk management, marketing management sector through supervision and inspection found problems, should be assigned the investigators are corrected in a timely manner. 27th the fifth chapter penalty under any of the following acts, then the relevant provisions to punish the investigators, according to the Bank. To constitute a crime shall be investigated for criminal responsibility: (A) on the business that are not involved in the investigation, issued a survey. (B) customer credit information are not thorough verification. (Iii) to participate in credit customer survey is not in place, customers and data is incomplete, untrue; he knows bear a counterfeited clients issuing credit. (D) does not provide for due diligence of credit business, pre-loan investigation form, concealing facts or providing false information or should be found in a normal investigation failed to discover the risk factors, lead to the review and approval policy errors, loan risk. (Five) on loan guarantees of survey not in place, not by provides on arrived, and pledge real for field verification, and assessment, and identification and registration, not according to provides on guarantor of guarantees qualification and guarantees capacity for survey verified, led to guarantees loan lost authenticity, and legitimacy, and effectiveness of; cycle loan business in the of mortgage