资源描述：
《北京理工大学数据结构实验报告实验三》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《数据结构与算法设计》实验报告——实验三学院：班级：学号：姓名：一、实验目的1.通过实验实践、巩固二叉树和队列的相关操作；2.熟悉VC环境，加强编程、调试的练习；3.用C语言实现二叉树和队列的抽象数据类型；4.用C语言编写递归函数，实现生成二叉树和遍历二叉树；5.用队列实现二叉树的层次遍历；6.理论知识与实际问题相结合，利用上述基本操作用多种方式遍历二叉树。二、实验内容1、遍历二叉树。请输入一棵二叉树的扩展的前序序列，经过处理后生成一棵二叉树，然后对于该二叉树输出前序、中序和后序遍历序列。2、选做：按层次遍历二叉树。三、程序设计1、概要设计为实现
2、上述程序功能，需要建立抽象数据类型：二叉树和队列。（1）、定义抽象数据类型二叉树的抽象数据类型定义为：ADTBinaryTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D=Φ，则R=Φ，称BinaryTree为空二叉树；若D≠Φ，则R={H}，H是如下二元关系；（1）在D中存在惟一的称为根的数据元素root，它在关系H下无前驱；（2）若D-{root}≠Φ，则存在D-{root}={D1,Dr}，且D1∩Dr=Φ；（3）若D1≠Φ，则D1中存在惟一的元素x1，∈H，且存在D1上的关系H1⊆H；若Dr≠Φ，则
3、Dr中存在惟一的元素xr，∈H，且存在上的关系Hr⊆H；H={,,H1,Hr}；（4）(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树；(Dr,{Hr})是一棵符合本定义的二叉树，称为根的右子树。基本操作：CreatBiTree(BiTree&T)操作结果：按先序次序建立二叉链表表示的二叉树TPreOrderTraverse(BiTreeT)初始条件：二叉树T已经存在操作结果：先序遍历二叉树T，对每个结点输出其数据元素InOrderTraverse(BiTreeT)初始条件：二叉树T
4、已经存在操作结果：中序遍历二叉树T，对每个结点输出其数据元素PostOrderTraverse(BiTreeT)初始条件：二叉树T已经存在操作结果：后序遍历二叉树T，对每个结点输出其数据元素LevelOrderTraverse(BiTreeT)初始条件：二叉树T已经存在操作结果：层次遍历二叉树T，对每个结点输出其数据元素}ADTBinaryTree队列的抽象数据类型定义为：ADTStack{数据对象：D={ai
5、ai∈ElemSet,i=1,2,3……,n,n≥0}数据关系：R1={
6、ai∈D,i=1,2,……,n}约定其中a1
7、端为队列头，an端为队列尾基本操作：InitQueue(&Q)功能：构造一个空队列Q。EnQueue(&Q,e)功能：将元素e插入Q的队尾。DeQueue(&Q,&e)功能：删除Q的队头元素。}ADTStack⑵主程序流程主程序先调用CreatBiTree(BiTree&T)函数，根据输入的先序序列构造出一棵二叉树，再依次调用PreOrderTraverse(BiTreeT)，InOrderTraverse(BiTreeT)，PostOrderTraverse(BiTreeT)，LevelOrderTraverse(BiTreeT)函数对该二叉树
8、进行先序、中序、后序、层次遍历并输出结果。⑶模块调用关系由主函数调用生成二叉树模块，调用先序、中序、后序遍历模块依次输出，调用层次遍历模块，调用队列的建立、插入、删除等模块，完成层次遍历并输出。⑷流程图生成二叉树CreatBiTree生成二叉树CreatBiTree开始生成二叉树CreatBiTree先序遍历并输出PreOrderTraverse中序遍历并输出InOrderTraverse后序遍历并输出PostOrderTraverse层次遍历并输出LevelOrderTraverse结束2、详细设计(1)、宏定义#defineMAXSIZE10
9、0//最大队列长度#defineOK1//操作无误#defineERROR0//操作有误#defineOVERFLOW-2//溢出（2）、抽象数据类型定义typedefintStatus;//函数类型typedefcharElemType;//二叉树的元素类型typedefstructBiTNode{//定义二叉树ElemTypedata;structBiTNode*lchild,*rchild;//左孩子和右孩子的指针}BiTNode,*BiTree;typedefBiTreeQElemType;//队列的元素类型typedefstruct{/
10、/定义队列QElemType*base;//初始化时分配存储空间的基址intfront;//队头指针，指向队头元素intrear;//队
