下载此文档

树与二叉树的转换(数据结构与算法-课程设计).zip


文档分类:IT计算机 | 页数:约21页 举报非法文档有奖
1/21
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/21 下载此文档
文档列表 文档介绍
河南工程学院《数据结构与算法》课程设计
成果报告
树与二叉树的转换
题 目
树与二叉树的转换
考核项目
考核内容
得分
平时考核
(30分)出勤情况、态度、效率;知识掌握情况、基本操作技能、知识应用能力、获取知识能力
系统设计
(20分)分析系统的功能模块
编程调试
(20分)实现系统的各个功能模块,并完成调试
回答问题
(15分)回答老师针对课程设计提出的问题
课程设计报告撰写
(10分)严格按照规范要求完成课程设计报告
源代码
(5分)按照规范要求完成课程设计源代码的排版
总 评 成 绩
指导教师评语:

日期: 年 月 日
目 录
目 录 3
1 课程设计目标与任务 4
1.1 课程设计目标 4
1.2 课程设计任务 4
2 分析与设计 4
2.1 题目需求分析 4
2.2 存储结构设计 4
2.2.1树的双亲表存储表示 5
2.2.2树的孩子链表存储表示 5
2.2.3二叉树的顺序存储表示 6
2.2.4二叉树的二叉链表存储表示 6
2.3 算法描述 7
2.3.1前序遍历二叉树的递归算法 7
2.3.2后序遍历二叉树的递归算法 7
2.3.3前序非递归算法 7
2.3.4后序非递归算法 8
2.3.5层次序遍历算法 8
2.3.6树与二叉树的转换算法 8
2.4 程序流程图 9
2.5 测试程序说明 10
3 程序清单 10
4 测试 15
4.1 测试数据 15
4.2测试结果分析 18
参考文献 20
1 课程设计目标与任务
1.1 课程设计目标
(1)了解和掌握树的相关概念、遍历和存储表达方法。
(2)了解和掌握二叉树的概念及性质、遍历和算法的实现。
(3)能够编码实现树与二叉树之间的转换,具备初步的独立分析和设计能力。
(4)在实际应用中学会运用树,能够理解、设计、分析和应用程序。
(5)初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。
1.2 课程设计任务
(1)实现树与二叉树的转换;
(2)能借助语言环境实现图形显示功能,以便将抽象的数据结构以图形方式显示出来,将复杂的运行过程以动态方式显示出来;
(3)给出若干例程,演示通过调用自己所缩写程序来实现相关问题的求解。
2 分析与设计
编辑算法,实现树与二叉树转换,利用双亲表示法和树的孩子链表来实现树的遍历算法,以及树的表示及其遍历操作,并建立树与二叉树的对应关系。
2.1 题目需求分析
1.根据给定二叉树的先序遍历结果,构造出该二叉树;按先序次序输入二叉树中结点的值(一个字符),空格字符表示空树。
2.给出该二叉树的递归前序和后序遍历结果。用栈实现非递归前序、后序的遍历的。还有对树的层序遍历以及树与二叉树的转换。
3. 以字符输入,若要实现终端结点,最后以回车键建入数据。
2.2 存储结构设计
二叉树是另一种树结构,他的特点是每个结点至多有两棵子树,并且,二叉树的子树有左右之分,其次序不能颠倒。
2.2.1树的双亲表存储表示
假设以一组连续空间存储树的结点,同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置,其形式说明如下:
#define MAX_TREE_SIZE 100
typedef struct PTNode{ //结点结构
TElemType data;
Int parent; //双亲结构
}PTNode;
typedef struct{ //树结构
PTNode nodes[MAX_TREE_SIZE];
INT R,N; //根的位置和结点数
}PTree;
2.2.2树的孩子链表存储表示
把每个结点的孩子结点排列起来,看成是一个线性表,且以单链表作存储结构,则n个结点有n个孩子链表。而n个头指针又组成一个线性表,为了便于查找,可采用顺序存储结构,这种存储结构可形式地说明如下:
typedef struct CTNode{ //孩子结点
int child;
struct CTNode *next;
}*ChildPtr;
typedef struct {
TElemType data;
ChildPtr fir

树与二叉树的转换(数据结构与算法-课程设计) 来自淘豆网www.taodocs.com转载请标明出处.

非法内容举报中心
文档信息