基于层次遍历的二叉树算法设计.doc

1 题目: 基于层次遍历的二叉树算法设计初始条件: 理论:学习了《数据结构》课程,掌握了基本的数据结构和常用的算法; 实践:计算机技术系实验室提供计算机及软件开发环境。要求完成的主要任务: ( 包括课程设计工作量及其技术要求,以及说明书撰写等具体要求) 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日 2 ?????????????????本程序设计实现二叉树的层次遍历,该程序主要部分包括:创建二叉树,按层次遍历二叉树。.????二叉树,队列,二叉链表,数据结构??????树型结构是一类重要的非线性数据结构,其中一树和二叉树最重要。树结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构够可以用树来形象表示。树在计算机领域中也得到了广泛应用,如在编译程序中,可以用树来表示源程序的语法结构。二叉树是一种非线性数据结构,对它进行操作时总需要对每个数据逐一进行操作,这样就存在一个操作顺序问题,由此提出了二叉树的遍历操作问题,所谓遍历二叉树就是按某种顺序访问二叉树中某个结点一次且仅一次的过程,。??????: ???行输入数据构造二叉树。???用队列存储二叉树结点。???算法实现层次遍历。???实现过程:A:初始,系统开始运行后,要先构造二叉树,先输入根结点数据信息。 B:根据提示信息输入其左子树,若没有左子树则输入“-1”。 C:根据提示信息输入其右子树,若没有右子树则输入“-1”。 D :在二叉树构造完成之后程序会自动按层次遍历二叉树,并且输出相应结点数据信息。 E:在完成上述过程之后按任意键结束程序。?????????????????? 3 typedef struct Bitnode /*树的链式存储*/ {BitTreeElementType data; struct Bitnode *lchild; /*左孩子*/ struct Bitnode *rchild; /*右孩子*/ }BTnode,*BitTree; ??????? QueueElemtype data[QUEUESIZE]; int front; /*队列的头指针*/ int rear; /*队列的尾指针*/ }queue; ?????????????? main() {“输入结点数据”; 初始化二叉树; “层次遍历二叉树”; 层次遍历二叉树; } ??????????? Statu CreateBitTree(BitTree *T) {为树指针 T分配空间; 输出“输入数据”; 存储输入数据; if(出入数据==空字符) 4 {结点不存储信息; }else {结点存储输入的信息; 输出“创建左子树”; CreateBitTree(&((*T)->lchild)); 输出“创建右子树”; CreateBitTree(&((*T)->rchild)); }} ???????????? Statu LayerTravelBitTree(BitTree T) {创建队列 tq; 向队列 tq尾插入 T; while (队头非空时){访问队头元素; 将树左子树插入队尾; 将树右子树插入队尾; }} ????????? int CreateQueue(queue *q) {对头指针和队尾指针相等; } 5 ??????????? int EnQueue(queue *q, QueueElemtype c) {队尾指针加 1; if(队尾指针超过队列长度) {输出“OVERFLOW ”; 退出程序; }将c存为队尾元素; } ??????????? Statu DeQueue(queue *q, QueueElemtype *ret) {if(队头指针和队尾指针相等) {返回错误; }头指针加 1; 将队头元素存于 ret 中; } ????????? Statu VisitData(BitTreeElementType data) {输出结点存储的信息; } ?????????程序用链式存储结构和队列分别存储二叉树和二叉树的结点。一方面采用队列存储 6 结点