二叉树实验报告

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

专 业 计算机科学与技术 班 级 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;

四、功能设计

（一）主控菜单设计

程序运行后，输入提示，如下：“创建二叉树，请按前序序列输入各节点值：” 正确输入二叉树后，提示“已成功创建二叉树”

（二）程序模块结构

由课题要求可将程序划分为以下几个模块（即实现程序功能所需的函数）：  创建二叉树的函数void CreateBiTree(BiTree &T);

 二叉树的前序遍历函数 Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType));  二叉树的中序遍历函数Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType));  二叉树的后序遍历函数Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType))；  最简单的visit函数Status Visit(TElemType e);

（三）函数调用关系

程序的主要结构（函数调用关系）如下图所示。

其中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) 主菜单显示如下：

代码描述：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) 建立二叉树及各种遍历：

六、结束语

本设计完成了课题要求的任务，较熟练地建立了二叉树，实现了各种遍历算法设计了较便捷的操作界面。

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

专 业 计算机科学与技术 班 级 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;

四、功能设计

（一）主控菜单设计

程序运行后，输入提示，如下：“创建二叉树，请按前序序列输入各节点值：” 正确输入二叉树后，提示“已成功创建二叉树”

（二）程序模块结构

由课题要求可将程序划分为以下几个模块（即实现程序功能所需的函数）：  创建二叉树的函数void CreateBiTree(BiTree &T);

 二叉树的前序遍历函数 Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType));  二叉树的中序遍历函数Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType));  二叉树的后序遍历函数Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType))；  最简单的visit函数Status Visit(TElemType e);

（三）函数调用关系

程序的主要结构（函数调用关系）如下图所示。

其中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) 主菜单显示如下：

代码描述：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) 建立二叉树及各种遍历：

六、结束语

本设计完成了课题要求的任务，较熟练地建立了二叉树，实现了各种遍历算法设计了较便捷的操作界面。


相关文章

  • 六年级科学下册实验计划报告单通知单一套

    • 小学科学六年级科学下册实验计划/报告单/通知单 实验是自然科学研究中十分重要的认识方法,它对于激发儿童的科学志趣, 培养儿童的科学能力,提高儿童的科学素质都有着十分重要的意义.在新课程理 念的引领下,在总结以往经验的基础上,特制定以下实验教 ...查看


  • 机能学实验报告中的问题分析

    • ・408・ 山西医科大学学报:基础医学教育版,2010年4月,12(4) 机能学实验报告中的问题分析 芜湖 241002)朱海龙, 张根葆 (皖南医学院病理生理学教研室, 摘要: 机能学实验报告是培养医学生科研写作能力的重要途径,,并在此基 ...查看


  • 实验室设备项目可行性研究报告

    • 实验室设备项目可行性研究报告 核心提示:实验室设备项目投资环境分析,实验室设备项目背景和发展概况,实验室设备项目建设的必要性,实验室设备行业竞争格局分析,实验室设备行业财务指标分析参考,实验室设备行业市场分析与建设规模,实验室设备项目建设条 ...查看


  • 重庆大学数据库实验报告2

    • <数据库系统>实验报告 备注: 1.教师在布置需撰写实验报告的实验前,应先将报告书上的"实验题 目"."实验性质"."实验目的"."实验项目内容"等 ...查看


  • 九龙镇中心小学科学实验报告单(3-6年级)

    • 教科版小学科学实验报告单 学校 九龙镇中心小学 年级 六 时间 实验名称 观察植物 小组成员 实验目的 观察小草和大树的相同点和不同点 实验器材 小草(多种).大树(多种).放大镜 1.观察准备好的小草的根.茎.叶.花.果实.种子 的特点: ...查看


  • (人教版)初中化学实验报告带答案报告

    • 97中学化学实验报告 八年级＿＿班0801号 姓名＿＿＿＿＿＿＿＿＿ 实验日期＿＿＿＿年＿＿月＿＿日 实验名称 用实验证明我们吸入的空气和呼出的气体中的氧 气含量有什么不同 实验目的 氧气可以使带火星的木条复燃,木条燃烧越旺,说明氧气 含量 ...查看


  • 教科版2015实验报告单(表格)

    • 科目:科学 实验名称:体验静电现象 指导教师: 年级: 填报告人: 实验日期: 同组实验人: 科目:科学 实验名称:让小灯泡发光 指导教师: 年级: 填报告人: 实验日期: 同组实验人: 科目:科学 实验名称:带灯座的电路 指导教师: 年级 ...查看


  • 实训指导手册

    • 实训指导手册 所在院系 所学专业 班级学号 学生姓名 指导教师 二零一一年一月二日 编 写 说 明 21世纪是经济全球化的世纪,也是国际金融环境面临巨大挑战的 世纪,更是全球外汇市场各种金融创新活动层出不穷的世纪.外汇市场是发生金融危机的主 ...查看


  • 进出口业务情景模拟实验报告该

    • 内蒙古工业大学进出口业务情景模拟实验报告目实验目的录„„„„„„„„„„„„„„„„„„„„„„„„„„„„„ 1 „„„„„„„„„„„„„„„„„„„„„„„ 2 „„„„„„„„„„„„„„„„„„„„„„„„„2 „„„„„„„„„ ...查看


  • 综合布线实验报告

    • 四川师范大学计算机学院 实 验 报 告 册 院系名称: 计算机科学学院 课程名称: 网络综合布线系统技术 实验学期年至 第 二学期 专业班级: 网络工程 姓名: 张晓丽 学号:2009110171 指导教师: 汤波 实验最终成绩: 实验报告 ...查看


热门内容