《北理工数据结构实验三.doc》由会员分享，可在线阅读，更多相关《北理工数据结构实验三.doc（10页珍藏版）》请在三一办公上搜索。
1、精选优质文档-倾情为你奉上数据结构与算法设计实验报告实验三学院： 班级： 学号： 姓名： 一、实验目的 1. 通过实验实践、巩固二叉树和队列的相关操作；2. 熟悉VC环境，加强编程、调试的练习；3. 用C语言实现二叉树和队列的抽象数据类型；4. 用C语言编写递归函数，实现生成二叉树和遍历二叉树；5. 用队列实现二叉树的层次遍历；6. 理论知识与实际问题相结合，利用上述基本操作用多种方式遍历二叉树。二、实验内容 1、遍历二叉树。请输入一棵二叉树的扩展的前序序列，经过处理后生成一棵二叉树，然后对于该二叉树输出前序、中序和后序遍历序列。2、选做：按层次遍历二叉树。三、程序设计 1、概要设计为实现上述
2、程序功能，需要建立抽象数据类型：二叉树和队列。（1） 、定义抽象数据类型二叉树的抽象数据类型定义为：ADT BinaryTree 数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D=，则R=，称BinaryTree为空二叉树； 若D，则R=H，H是如下二元关系； （1）在D中存在惟一的称为根的数据元素root，它在关系H下无前驱； （2）若D-root，则存在D-root=D1,Dr，且D1Dr =； （3）若D1，则D1中存在惟一的元素x1，H，且存在D1上的关系H1 H；若Dr，则Dr中存在惟一的元素xr，H，且存在上的关系Hr H；H=,H1,Hr； （4）(D1,H1)是一
3、棵符合本定义的二叉树，称为根的左子树；(Dr,Hr)是一棵符合本定义的二叉树，称为根的右子树。基本操作：CreatBiTree(BiTree &T)操作结果：按先序次序建立二叉链表表示的二叉树TPreOrderTraverse(BiTree T)初始条件：二叉树T已经存在 操作结果：先序遍历二叉树T ，对每个结点输出其数据元素InOrderTraverse(BiTree T)初始条件：二叉树T已经存在 操作结果：中序遍历二叉树T ，对每个结点输出其数据元素PostOrderTraverse(BiTree T)初始条件：二叉树T已经存在 操作结果：后序遍历二叉树T ，对每个结点输出其数据元素Le
4、velOrderTraverse(BiTree T)初始条件：二叉树T已经存在 操作结果：层次遍历二叉树T ，对每个结点输出其数据元素 ADT BinaryTree队列的抽象数据类型定义为：ADT Stack 数据对象：D=ai|aiElemSet,i=1,2,3,n,n0数据关系：R1= |aiD,i=1,2,n 约定其中a1端为队列头，an端为队列尾基本操作：InitQueue(&Q) 功能：构造一个空队列Q。EnQueue(&Q, e ) 功能：将元素e插入Q的队尾。DeQueue(&Q,&e) 功能：删除Q的队头元素。ADT Stack主程序流程主程序先调用CreatBiTree(Bi
5、Tree &T)函数，根据输入的先序序列构造出一棵二叉树，再依次调用PreOrderTraverse(BiTree T)，InOrderTraverse(BiTree T)，PostOrderTraverse(BiTree T)，LevelOrderTraverse(BiTree T)函数对该二叉树进行先序、中序、后序、层次遍历并输出结果。模块调用关系由主函数调用生成二叉树模块，调用先序、中序、后序遍历模块依次输出，调用层次遍历模块，调用队列的建立、插入、删除等模块，完成层次遍历并输出。流程图生成二叉树CreatBiTree生成二叉树CreatBiTree开始生成二叉树CreatBiTree先
6、序遍历并输出PreOrderTraverse中序遍历并输出InOrderTraverse后序遍历并输出PostOrderTraverse层次遍历并输出LevelOrderTraverse结束 2、详细设计 (1)、宏定义#define MAXSIZE 100 /最大队列长度#define OK 1 /操作无误#define ERROR 0 /操作有误#define OVERFLOW -2 /溢出（2）、抽象数据类型定义typedef int Status; /函数类型typedef char ElemType; /二叉树的元素类型typedef struct BiTNode/定义二叉树Elem
7、Type data; struct BiTNode * lchild, * rchild; /左孩子和右孩子的指针BiTNode, * BiTree;typedef BiTree QElemType; /队列的元素类型typedef struct/定义队列QElemType * base; /初始化时分配存储空间的基址int front; /队头指针，指向队头元素int rear; /队尾指针，指向队尾元素的下一个位置SqQueue;（3）、操作算法程序实现：Status InitQueue(SqQueue &Q ) /构造一个空队列QQ.base=(QElemType * )malloc (
8、MAXSIZE * sizeof (QElemType);if ( !Q.base ) exit (OVERFLOW); /存储分配失败Q.front = Q.rear = 0;return OK;/InitQueueStatus EnQueue( SqQueue &Q, QElemType e )/将元素e插入队尾if ( (Q.rear+1)%MAXSIZE=Q.front ) return ERROR ; /队满Q.baseQ.rear = e ; /将元素e插入队尾Q.rear = (Q.rear+1)%MAXSIZE; /修改队尾指针return OK;/EnQueueStatus
9、DeQueue( SqQueue &Q, QElemType &e ) /删除队头元素，用e返回其值，并返回OK；否则返回ERRORif ( Q.rear=Q.front ) return ERROR ; /队空e = Q.baseQ.front ; / 取队头元素 eQ.front = (Q.front+1)%MAXSIZE; /修改队头指针return OK;/EnQueueint CreateBiTree(BiTree &T)/按先序次序建立二叉链表表示的二叉树TElemType ch;scanf (%c,&ch);if ( ch = ) T=NULL; / 若ch= 则表示空子树 el
10、se if ( ! (T=( BiTNode * ) malloc( sizeof( BiTNode ) ) ) )exit(OVERFLOW);T-data = ch; / 建立（根）结点 CreateBiTree(T-lchild); / 递归构造左子树链表CreateBiTree(T-rchild); / 递归构造右子树链表 return OK;/CreateBiTreevoid PreOrderTraverse( BiTree T) /先序遍历以T为根结点指针的二叉树if (T) /若二叉树不为空 printf(%c,T-data); /访问根结点 PreOrderTraverse(T
11、-lchild); /先序遍历T的左子树 PreOrderTraverse(T-rchild); /先序遍历T的右子树 /PreOrderTraversevoid InOrderTraverse( BiTree T) /中序遍历以T为根结点指针的二叉树if (T) /若二叉树不为空 InOrderTraverse(T-lchild); /中序遍历T的左子树 printf(%c,T-data); /访问根结点 InOrderTraverse(T-rchild); /中序遍历T的右子树 /InOrderTraversevoid PostOrderTraverse( BiTree T) /后序遍历以
12、T为根结点指针的二叉树if (T) /若二叉树不为空 PostOrderTraverse(T-lchild); /后序遍历T的左子树 PostOrderTraverse(T-rchild); /后序遍历T的右子树printf(%c,T-data); /访问根结点 /PostOrderTraversevoid LevelOrderTraverse(BiTree T)/层次遍历以T为根结点指针的二叉树SqQueue q;BiTree p;InitQueue(q);if(T) EnQueue(q,T); /队头元素进队列while(!(q.front=q.rear)DeQueue(q,p); pri
13、ntf(%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键结
14、束。3. 屏幕输出以上二叉树的先序、中序、后序、层次遍历结果，按任意键退出程序。六、程序运行结果测试一： 测试二：测试三：七、程序清单#include stdio.h#include stdlib.h#define MAXSIZE 100 /最大队列长度#define OK 1 /操作无误#define ERROR 0 /操作有误#define OVERFLOW -2 /溢出typedef int Status; /函数类型typedef char ElemType; /二叉树的元素类型typedef struct BiTNode/定义二叉树ElemType data; struct BiTN
15、ode * lchild, * rchild; /左孩子和右孩子的指针BiTNode, * BiTree;typedef BiTree QElemType; /队列的元素类型typedef struct/定义队列QElemType * base; /初始化时分配存储空间的基址int front; /队头指针，指向队头元素int rear; /队尾指针，指向队尾元素的下一个位置SqQueue;Status InitQueue(SqQueue &Q ) /构造一个空队列QQ.base=(QElemType * )malloc (MAXSIZE * sizeof (QElemType);if ( !
16、Q.base ) exit (OVERFLOW); /存储分配失败Q.front = Q.rear = 0;return OK;/InitQueueStatus EnQueue( SqQueue &Q, QElemType e )/将元素e插入队尾if ( (Q.rear+1)%MAXSIZE=Q.front ) return ERROR ; /队满Q.baseQ.rear = e ; /将元素e插入队尾Q.rear = (Q.rear+1)%MAXSIZE; /修改队尾指针return OK;/EnQueueStatus DeQueue( SqQueue &Q, QElemType &e )
17、 /删除队头元素，用e返回其值，并返回OK；否则返回ERRORif ( Q.rear=Q.front ) return ERROR ; /队空e = Q.baseQ.front ; / 取队头元素 eQ.front = (Q.front+1)%MAXSIZE; /修改队头指针return OK;/EnQueueint CreateBiTree(BiTree &T)/按先序次序建立二叉链表表示的二叉树TElemType ch;scanf (%c,&ch);if ( ch = ) T=NULL; / 若ch= 则表示空子树 else if ( ! (T=( BiTNode * ) malloc(
18、sizeof( BiTNode ) ) ) )exit(OVERFLOW);T-data = ch; / 建立（根）结点 CreateBiTree(T-lchild); / 递归构造左子树链表CreateBiTree(T-rchild); / 递归构造右子树链表 return OK;/CreateBiTreevoid PreOrderTraverse( BiTree T) /先序遍历以T为根结点指针的二叉树if (T) /若二叉树不为空 printf(%c,T-data); /访问根结点 PreOrderTraverse(T-lchild); /先序遍历T的左子树 PreOrderTraver
19、se(T-rchild); /先序遍历T的右子树 /PreOrderTraversevoid InOrderTraverse( BiTree T) /中序遍历以T为根结点指针的二叉树if (T) /若二叉树不为空 InOrderTraverse(T-lchild); /中序遍历T的左子树 printf(%c,T-data); /访问根结点 InOrderTraverse(T-rchild); /中序遍历T的右子树 /InOrderTraversevoid PostOrderTraverse( BiTree T) /后序遍历以T为根结点指针的二叉树if (T) /若二叉树不为空 PostOrde
20、rTraverse(T-lchild); /后序遍历T的左子树 PostOrderTraverse(T-rchild); /后序遍历T的右子树printf(%c,T-data); /访问根结点 /PostOrderTraversevoid LevelOrderTraverse(BiTree T)/层次遍历以T为根结点指针的二叉树SqQueue q;BiTree p;InitQueue(q);if(T) EnQueue(q,T); /队头元素进队列while(!(q.front=q.rear)DeQueue(q,p); printf(%c,p-data); /输出队头元素if(p-lchild)
21、 EnQueue(q,p-lchild); /左子树进队列if(p-rchild) EnQueue(q,p-rchild); /右子树进队列int main()BiTree T;printf(请按先序遍历输入二叉树n注意：若该子树为空则输入空格n);CreateBiTree(T);printf(先序遍历的结果为：n);PreOrderTraverse(T);printf(n);printf(中序遍历的结果为：n);InOrderTraverse(T);printf(n);printf(后序遍历的结果为：n);PostOrderTraverse(T);printf(n);printf(层次遍历的结果为：n);LevelOrderTraverse(T);printf(n);return 0;专心-专注-专业
