北理工数据结构实验三

《数据结构与算法设计》实验报告——实验三学院：班级：学号：姓名：一、实验目的1.通过实验实践、巩固二叉树和队列的相关操作；2.熟悉VC环境，加强编程、调试的练习；3.用C语言实现二叉树和队列的抽象数据类型；4.用C语言编写递归函数，实现生成二叉树和遍历二叉树；5.用队列实现二叉树的层次遍历；6.理论知识与实际问题相结合，利用上述基本操作用多种方式遍历二叉树。二、实验内容1、遍历二叉树。请输入一棵二叉树的扩展的前序序列，经过处理后生成一棵二叉树，然后对于该二叉树输出前序、中序和后序遍历序列。2、选做：按层次遍历二叉树。三、程序设计1、概要设计为实现上述程序功能，需要建立抽象数据类型：二叉树和队列。（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，root,x1∈H，且存在D1上的关系H1⊆H；若Dr≠Φ，则Dr中存在惟一的元素xr，root,xr∈H，且存在上的关系Hr⊆H；H={root,x1,root,xr,H1,Hr}；（4）(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树；(Dr,{Hr})是一棵符合本定义的二叉树，称为根的右子树。基本操作：CreatBiTree(BiTree&T)操作结果：按先序次序建立二叉链表表示的二叉树TPreOrderTraverse(BiTreeT)初始条件：二叉树T已经存在操作结果：先序遍历二叉树T，对每个结点输出其数据元素InOrderTraverse(BiTreeT)初始条件：二叉树T已经存在操作结果：中序遍历二叉树T，对每个结点输出其数据元素PostOrderTraverse(BiTreeT)初始条件：二叉树T已经存在操作结果：后序遍历二叉树T，对每个结点输出其数据元素LevelOrderTraverse(BiTreeT)初始条件：二叉树T已经存在操作结果：层次遍历二叉树T，对每个结点输出其数据元素}ADTBinaryTree队列的抽象数据类型定义为：ADTStack{数据对象：D={ai|ai∈ElemSet,i=1,2,3……,n,n≥0}数据关系：R1={ai-1,ai|ai∈D,i=1,2,……,n}约定其中a1端为队列头，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)函数对该二叉树进行先序、中序、后序、层次遍历并输出结果。⑶模块调用关系由主函数调用生成二叉树模块，调用先序、中序、后序遍历模块依次输出，调用层次遍历模块，调用队列的建立、插入、删除等模块，完成层次遍历并输出。⑷流程图开始生成二叉树CreatBiTree先序遍历并输出PreOrderTraverse中序遍历并输出InOrderTraverse后序遍历并输出PostOrderTraverse层次遍历并输出LevelOrderTraverse结束2、详细设计(1)、宏定义#defineMAXSIZE100//最大队列长度#defineOK1//操作无误#defineERROR0//操作有误#defineOVERFLOW-2//溢出（2）、抽象数据类型定义typedefintStatus;//函数类型typedefcharElemType;//二叉树的元素类型typedefstructBiTNode{//定义二叉树ElemTypedata;structBiTNode*lchild,*rchild;//左孩子和右孩子的指针}BiTNode,*BiTree;typedefBiTreeQElemType;//队列的元素类型typedefstruct{//定义队列QElemType*base;//初始化时分配存储空间的基址intfront;//队头指针，指向队头元素intrear;//队尾指针，指向队尾元素的下一个位置}SqQueue;（3）、操作算法程序实现：StatusInitQueue(SqQueue&Q){//构造一个空队列QQ.base=(QElemType*)malloc(MAXSIZE*sizeof(QElemType));if(!Q.base)exit(OVERFLOW);//存储分配失败Q.front=Q.rear=0;returnOK;}//InitQueueStatusEnQueue(SqQueue&Q,QElemTypee){//将元素e插入队尾if((Q.rear+1)%MAXSIZE==Q.front)returnERROR;//队满Q.base[Q.rear]=e;//将元素e插入队尾Q.rear=(Q.rear+1)%MAXSIZE;//修改队尾指针returnOK;}//EnQueueStatusDeQueue(SqQueue&Q,QElemType&e){//删除队头元素，用e返回其值，并返回OK；否则返回ERRORif(Q.rear==Q.front)returnERROR;//队空e=Q.base[Q.front];//取队头元素eQ.front=(Q.front+1)%MAXSIZE;//修改队头指针returnOK;}//EnQueueintCreateBiTree(BiTree&T){//按先序次序建立二叉链表表示的二叉树TElemTypech;scanf(%c,&ch);if(ch=='')T=NULL;//若ch==''则表示空子树else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T-data=ch;//建立（根）结点CreateBiTree(T-lchild);//递归构造左子树链表CreateBiTree(T-rchild);//递归构造右子树链表}returnOK;}//CreateBiTreevoidPreOrderTraverse(BiTreeT){//先序遍历以T为根结点指针的二叉树if(T)//若二叉树不为空{printf(%c,T-data);//访问根结点PreOrderTraverse(T-lchild);//先序遍历T的左子树PreOrderTraverse(T-rchild);//先序遍历T的右子树}}//PreOrderTraversevoidInOrderTraverse(BiTreeT){//中序遍历以T为根结点指针的二叉树if(T)//若二叉树不为空{InOrderTraverse(T-lchild);//中序遍历T的左子树printf(%c,T-data);//访问根结点InOrderTraverse(T-rchild);//中序遍历T的右子树}}//InOrderTraversevoidPostOrderTraverse(BiTreeT){//后序遍历以T为根结点指针的二叉树if(T)//若二叉树不为空{PostOrderTraverse(T-lchild);//后序遍历T的左子树PostOrderTraverse(T-rchild);//后序遍历T的右子树printf(%c,T-data);//访问根结点}}//PostOrderTraversevoidLevelOrderTraverse(BiTreeT){//层次遍历以T为根结点指针的二叉树SqQueueq;BiTreep;InitQueue(q);if(T)EnQueue(q,T);//队头元素进队列while(!(q.front==q.rear)){DeQueue(q,p);printf(%c,p-data);//输出队头元素if(p-lchild)EnQueue(q,p-lchild);//左子树进队列if(p-rchild)EnQueue(q,p-rchild);//右子树进队列}}四、程序调试分析1.程序中用到的未定义的字符串要进行宏定义；2.输入二叉树时要注意用空格代替子树为空；3.二叉树的层次遍历可以借助队列来实现；4.先定义二叉树，再定义队列元素的数据结构为二叉树类型，顺序颠倒会出错。五、用户使用说明1.本程序的运行环境为DOS操作系统，执行文件为：实验三.exe，双击打开文件。2.进入程序后，根据提示输入先序遍历的二叉树，按Enter键结束。3.屏幕输出以上二叉树的先序、中序、后序、层次遍历结果，按任意键退出程序。六、程序运行结果测试一：测试二：测试三：七、程序清单#includestdio.h#includestdlib.h#defineMAXSIZE100//最大队列长度#defineOK1//操作无误#defineERROR0//操作有误#defineOVERFLOW-2//溢出typedefintStatus;//函数类型typedefcharElemType;//二叉树的元素类型typedefstructBiTNode{//定义二叉树ElemTypedata;structBiTNode*lchild,*rchild;//左孩子和右孩子的指针}BiTNode,*BiTree;typedefBiTreeQElemType;//队列的元素类型typedefstruct{//定义队列QElemType*base;//初始化时分配存储空间的基址intfront;//队头指针，指向队头元素intrear;//队尾指针，指向队尾元素的下一个位置}SqQueue;StatusInitQueue(SqQueue&Q){//构造一个空队列QQ.base=(QElemType*)malloc(MAXSIZE*sizeof(QElemType));if(!Q.base)exit(OVERFLOW);//存储分配失败Q.front=Q.rear=0;returnOK;}//InitQueueStatusEnQueue(SqQueue&Q,QElemTypee){//将元素e插入队尾if((Q.rear+1)%MAXSIZE==Q.front)returnERROR;//队满Q.base[Q.rear]=e;//将元素e插入队尾Q.rear=(Q.rear+1)%MAXSIZE;//修改队尾指针returnOK;}//EnQueueStatusDeQueue(SqQueue&Q,QElemType&e){//删除队头元素，用e返回其值，并返回OK；否则返回ERRORif(Q.rear==Q.front)returnERROR;//队空e=Q.base[Q.front];//取队头元素eQ.front=(Q.front+1)%MAXSIZE;//修改队头指针returnOK;}//EnQueueintCreateBiTree(BiTree&T){//按先序次序建立二叉链表表示的二叉树TElemTypech;scanf(%c,&ch);if(ch=='')T=NULL;//若ch==''则表示空子树else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T-data=ch;//建立（根）结点CreateBiTree(T-