基于层次遍历的二叉树算法设计.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 日 验收程序，提交设计报告书指导教师签名：指导教师签名： 20072007 年年 7 7 月月 2 2 日日系主任（或责任教师）签名：系主任（或责任教师）签名： 20072007 年年 7 7 月月 2 2 日日武汉理工大学《数据结构》课程设计说明书2基于层次遍历的二叉树算法设计摘要：本程序设计实现二叉树的层次遍历，该程序主要部分包括：创建二叉树，按层次遍历二叉树。

关键字：二叉树，队列，二叉链表，数据结构 . 0.引言：树型结构是一类重要的非线性数据结构，其中一树和二叉树最重要树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构够可以用树来形象表示树在计算机领域中也得到了广泛应用，如在编译程序中，可以用树来表示源程序的语法结构二叉树是一种非线性数据结构，对它进行操作时总需要对每个数据逐一进行操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作问题，所谓遍历二叉树就是按某种顺序访问二叉树中某个结点一次且仅一次的过程，这里的访问可以是输出.比较.更新.查看元素内容等各种操作 1.需求分析：1.1行输入数据构造二叉树1.2用队列存储二叉树结点1.3算法实现层次遍历1.4实现过程:A：初始，系统开始运行后，要先构造二叉树，先输入根结点数据信息B：根据提示信息输入其左子树，若没有左子树则输入“-1” C：根据提示信息输入其右子树，若没有右子树则输入“-1” D：在二叉树构造完成之后程序会自动按层次遍历二叉树，并且输出相应结点数据信息E：在完成上述过程之后按任意键结束程序 2.数据结构设计：2.1 树的链式存储typedef struct Bitnode/*树的链式存储*/武汉理工大学《数据结构》课程设计说明书3{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 ( 出入数据==空字符){武汉理工大学《数据结构》课程设计说明书4结点不存储信息；}else{结点存储输入的信息；输出“创建左子树” ；CreateBitTree(输出“创建右子树” ；CreateBitTree(}}3.3 层次遍历二叉树模块Statu LayerTravelBitTree(BitTree T){创建队列 tq；向队列 tq 尾插入 T；while ( 队头非空时){访问队头元素；将树左子树插入队尾；将树右子树插入队尾；}}3.4 创建队列模块int CreateQueue(queue *q){对头指针和队尾指针相等；}3.5 插入队列元素模块武汉理工大学《数据结构》课程设计说明书5int EnQueue(queue *q, QueueElemtype c){队尾指针加 1；if (队尾指针超过队列长度){输出“OVERFLOW” ；退出程序；}将 c 存为队尾元素；}3.6 删除队列元素模块Statu DeQueue(queue *q, QueueElemtype *ret){if (队头指针和队尾指针相等){返回错误；}头指针加 1；将队头元素存于 ret 中；}3.7 访问结点模块Statu VisitData(BitTreeElementType data){输出结点存储的信息；}3.7 主要技术说明程序用链式存储结构和队列分别存储二叉树和二叉树的结点。

一方面采用队列存储结点是结合层次遍历二叉树和队列“先进先出”的特点综合考虑的，因为层次遍历即武汉理工大学《数据结构》课程设计说明书6从上到下从左到右依次遍历二叉树结点，而队列恰好可以从上到下从左到右顺序进队然后顺序出队，符合设计的要求另一方面采用二叉树的链式存储结构而非顺序存储结构是因为构造二叉树需用到递归算法，采用链式存储结构容易实现初始化二叉树的实现：首先输入根结点，若根结点非空则将其设为树的根结点，否则返回“FALSE” ；其次输入结点左子树，若非空则将其存为上一结点的左子树，否则输入右子树；若非空则将其存为上一结点的右子树，否则结束，完成二叉树初始化递归重复以上操作即可初始化二叉树本系统对用户在操作时可能进行的错误和违规操作，给出了基本的提示信息，以便用户在非法操作后得到意想不到的结果4.程序实现4.1 库函数#include /*I/O 函数*/#include “conio.h“4.2 定义宏#define QUEUESIZE 100 /*队列初始容量*/#define TRUE 1#define FALSE !TRUE#define Statu int#define BitTreeElementType int#define SHUJU “%d“#define END -14.3 定义全局变量typedef struct Bitnode/*树的链式存储*/{BitTreeElementType data;struct Bitnode *lchild;/*左孩子 */struct Bitnode *rchild;/*右孩子*/}BTnode,*BitTree;武汉理工大学《数据结构》课程设计说明书7typedef BitTree QueueElemtype；typedef struct/*定义数据结构*/{QueueElemtype data[QUEUESIZE];int front;/*队列的头指针*/int rear;/*队列的尾指针*/}queue;4.4 函数原型int CreateQueue(queue *q);/*创建队列*/int EnQueue(queue *q, QueueElemtype c);/*向队尾插入元素 c*/Statu DeQueue(queue *q, QueueElemtype *reb);/*队头元素出队用 reb 返回其值*/Statu CreateBitTree(BitTree *T);/*初始化二叉树*/Statu LayerTravelBitTree(BitTree T);/*层次遍历二叉树*/4.5 主函数main(){BitTree t;printf(“Input data to create bittree and '“);printf(SHUJU,END);printf(“' will make null tree.\n“);/*输入根结点 */CreateBitTree(/*初始化二叉树*/printf(“Layer order travel the tree:\n“);/*层次遍历二叉树*/LayerTravelBitTree(t);/*层次遍历二叉树*/武汉理工大学《数据结构》课程设计说明书8}4.6 初始化二叉树 Statu CreateBitTree(BitTree *T)/*初始化二叉树*/{BitTreeElementType inputdata;*T = (BitTree )malloc(sizeof(BTnode));printf(“Enter Data:“);/*输入数据*/fflush(stdin);scanf(SHUJU,if ( inputdata == END)*T = NULL;return FALSE;}else{(*T)->data = inputdata;/*将输入的数据存入结点*/printf(“Create left sub tree...lchild));/*递归循环输入左子树*/printf(“Create right sub tree...rchild));/*递归循环输入右子树*/return TRUE;}}4.7 层次遍历二叉树 Statu LayerTravelBitTree(BitTree T)/*层次遍历二叉树*/{武汉理工大学《数据结构》课程设计说明书9queue tq;/*队列 tq*/QueueElemtype res;/*用来返回对头元素*/CreateQueue(/*创建队列*/EnQueue(/*将 T 插入队尾*/while ( DeQueue(/*访问队头元素*/EnQueue(/*将结点左孩子插入队尾*/EnQueue(/*将结点右孩子插入队尾*/}}}4.8 创建空队列int CreateQueue(queue *q){q->front = -1;q->rear = -1;}4.9 队尾插入元素（结点入队）int EnQueue(queue *q, QueueElemtype c)/*将元素 c 插入队尾*/{q->rear++;/*尾指针加 1*/if (q->rear >= QUEUESIZE)/*若尾指针超出队列长度则提示错误*/武汉理工大学《数据结构》课程设计说明书10{printf(“Queue overflow!\n“);exit(0);}q->data[q->rear] = c;return 1;}4.10 队头元素出队Statu DeQueue(queue *q, QueueElemtype *ret)/*队头元素出队并用 ret返回其值*/{if (q->front == q->rear)/*若队列为空，则返回错误提示*/{return FALSE;}q->front++;/*头指针加 1*/*ret = q->data[q->front];return TRUE;}4.11 访问结点Statu VisitData(BitTreeElementType data){printf(SHUJU,data);printf(“\n“);return TRUE;武汉理工大学《数据结构》课程设计说明书11}4.124.12 程序运行结果程序运行结果主界面：结果分析结果分析：实验结果的排序完全正确。

程序可以实现用户自己构造二叉树，然 后实现对二叉树的层次遍历程序基本上满足了算法设计要求，但是仍有地方值得提 高，仍需完善 5.设计体会 通过课程设计自己对《数据结构》这门课程有了更深一层的了解，意识到了数据结构的重要性，。