- 1、本文档共22页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
基于层次遍历二叉树算法设计
题 目: 基于层次遍历的二叉树算法设计
初始条件:
理论:学习了《数据结构》课程,掌握了基本的数据结构和常用的算法;
实践:计算机技术系实验室提供计算机及软件开发环境。
要求完成的主要任务: (包括课程设计工作量及其技术要求,以及说明书撰写等具体要求)
1、系统应具备的功能:
(1)建立二叉树
(2)按层次遍历二叉树
2、数据结构设计;
3、主要算法设计;
4、编程及上机实现;
5、撰写课程设计报告,包括:
(1)设计题目;
(2)摘要和关键字;
(3)正文,包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、不足之处、设计体会;
(4)结束语;
(5)参考文献。
时间安排: 2007年7月2日-7日 (第18周)
7月2日 查阅资料
7月3日 系统设计,数据结构设计,算法设计
7月4日-5日 编程并上机调试
7月6日 撰写报告
7月7日 验收程序,提交设计报告书。
指导教师签名: 2007年7月2日
系主任(或责任教师)签名: 2007年7月2日
基于层次遍历的二叉树算法设计
摘要:本程序设计实现二叉树的层次遍历,该程序主要部分包括:创建二叉树,按层次遍历二叉树。.
关键字:二叉树,队列,二叉链表,数据结构
.
0.引言:
树型结构是一类重要的非线性数据结构,其中一树和二叉树最重要。树结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构够可以用树来形象表示。树在计算机领域中也得到了广泛应用,如在编译程序中,可以用树来表示源程序的语法结构。二叉树是一种非线性数据结构,对它进行操作时总需要对每个数据逐一进行操作,这样就存在一个操作顺序问题,由此提出了二叉树的遍历操作问题,所谓遍历二叉树就是按某种顺序访问二叉树中某个结点一次且仅一次的过程,这里的访问可以是输出.比较.更新.查看元素内容等各种操作。
1.需求分析:
1.1行输入数据构造二叉树。
1.2用队列存储二叉树结点。
1.3算法实现层次遍历。
1.4实现过程:
A:初始,系统开始运行后,要先构造二叉树,先输入根结点数据信息。
B:根据提示信息输入其左子树,若没有左子树则输入“-1”。
C:根据提示信息输入其右子树,若没有右子树则输入“-1”。
D:在二叉树构造完成之后程序会自动按层次遍历二叉树,并且输出相应结点数据信息。
E:在完成上述过程之后按任意键结束程序。
2.数据结构设计:
2.1树的链式存储
typedef struct Bitnode /*树的链式存储*/
{
BitTreeElementType data;
struct Bitnode *lchild; /*左孩子 */
struct Bitnode *rchild; /*右孩子*/
}BTnode,*BitTree;
2.2队列定义
QueueElemtype data[QUEUESIZE];
int front; /*队列的头指针*/
int rear; /*队列的尾指针*/
}queue;
3.算法设计
3.1主函数模块
main()
{
“输入结点数据”;
初始化二叉树;
“层次遍历二叉树”;
层次遍历二叉树;
}
3.2初始化二叉树模块
Statu CreateBitTree(BitTree *T)
{
为树指针T分配空间;
输出“输入数据”;
存储输入数据;
if ( 出入数据==空字符)
{
结点不存储信息;
}
else
{
结点存储输入的信息;
输出“创建左子树”;
CreateBitTree(((*T)-lchild));
输出“创建右子树”;
CreateBitTree(((*T)-rchild));
}
}
3.3层次遍历二叉树模块
Statu LayerTravelBitTree(BitTree T)
{
创建队列tq;
向队列tq尾插入T;
while ( 队头非空时)
{
访问队头元素;
将树左子树插入队尾;
将树右子树插入队尾;
}
}
3.4创建队列模块
int CreateQueue(queue *q)
{
对头指针和队尾指针相等;
}
3.5插入队列元素模块
int EnQueue(queue *q, QueueElemtype c)
{
队尾指针加1;
if (队尾指针超过队列长度)
{
输出“OVERFLOW”;
退出程序;
}
将c存为队尾元素;
}
3.6删除队列元素模块
Statu DeQueue(queue *q, QueueElemtype *ret)
{
i
文档评论(0)