北理工数据结构实验三
- 格式：docx
- 大小：57.31 KB
- 文档页数：12
北理工数据结构实验三
《数据结构与算法设计》
实验报告
——实验三
学院：
班级：
学号：
姓名：
一、实验目的
1.通过实验实践、巩固二叉树和队列的相关操作；
2.熟悉VC环境，加强编程、调试的练习；
3.用C语言实现二叉树和队列的抽象数据类型；
4.用C语言编写递归函数，实现生成二叉树和遍历二叉树；
5.用队列实现二叉树的层次遍历；
6.理论知识与实际问题相结合，利用上述基本操作用多种方式遍历二叉树。
二、实验内容
1、遍历二叉树。
请输入一棵二叉树的扩展的前序序列，经过处理后生成一棵二叉树，然后对于该二叉树输出前序、中序和后序遍历序列。
2、选做：按层次遍历二叉树。
三、程序设计
1、概要设计
为实现上述程序功能，需要建立抽象数据类型：二叉树和队列。
（1）、定义抽象数据类型
二叉树的抽象数据类型定义为：
ADT BinaryTree {
数据对象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≠Φ，则Dr中存在惟一的元素xr，∈H，且存在上的关系
Hr ?H；H={,,H1,Hr}；
（4）(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树；(Dr,{Hr})是一棵
符合本定义的二叉树，称为根的右子树。
基本操作：
CreatBiTree(BiTree &T)
操作结果：按先序次序建立二叉链表表示的二叉树T
PreOrderTraverse(BiTree T)
初始条件：二叉树T已经存在
操作结果：先序遍历二叉树T ，对每个结点输出其数据元素
InOrderTraverse(BiTree T)
初始条件：二叉树T已经存在
操作结果：中序遍历二叉树T ，对每个结点输出其数据元素
PostOrderTraverse(BiTree T)
初始条件：二叉树T已经存在
操作结果：后序遍历二叉树T ，对每个结点输出其数据元素
LevelOrderTraverse(BiTree T)
初始条件：二叉树T已经存在
操作结果：层次遍历二叉树T ，对每个结点输出其数据元素} ADT
BinaryTree
队列的抽象数据类型定义为： ADT Stack{
数据对象：D={ai|ai∈ElemSet,i=1,2,3……,n,n≥0}
数据关系：R1={ |ai∈D,i=1,2,……,n}
约定其中a1端为队列头，an端为队列尾
基本操作：
InitQueue(&Q)
功能：构造一个空队列Q。
EnQueue(&Q, e )
功能：将元素e插入Q的队尾。
DeQueue(&Q,&e)
功能：删除Q的队头元素。
}ADT Stack
⑵主程序流程
主程序先调用CreatBiTree(BiTree &T)函数，根据输入的先序序列构造出一棵二叉树，再依次调用PreOrderTraverse(BiTree T)，InOrderTraverse(BiTree T)，PostOrderTraverse(BiTree T)，LevelOrderTraverse(BiTree T)函数对该二叉树进行先序、中序、后序、层次遍历并输出结果。
⑶模块调用关系
由主函数调用生成二叉树模块，调用先序、中序、后序遍历模块依次输出，调用层次遍历模块，调用队列的建立、插入、删除等模块，完成层次遍历并输出。
⑷流程图 2、详细设计
(1)、宏定义
#define MAXSIZE 100 //最大队列长度
#define OK 1 //操作无误
#define ERROR 0 //操作有误
#define OVERFLOW -2 //溢出
（2）、抽象数据类型定义
typedef int Status; //函数类型
typedef char ElemType; //二叉树的元素类型
typedef struct BiTNode
{//定义二叉树 ElemType data; struct BiTNode * lchild, * rchild; //左孩子和右孩子的指针}BiTNode, * BiTree;
typedef BiTree QElemType; //队列的元素类型
typedef struct
{//定义队列
QElemType * base; //初始化时分配存储空间的基址
int front; //队头指针，指向队头元素
int rear; //队尾指针，指向队尾元素的下一个位置
}SqQueue;
（3）、操作算法程序实现：
Status InitQueue(SqQueue &Q )
{//构造一个空队列Q
Q.base=(QElemType * )
malloc (MAXSIZE * sizeof (QElemType));
if ( !Q.base ) exit (OVERFLOW); //存储分配失败
Q.front = Q.rear = 0;
return OK;
}//InitQueue
Status EnQueue( SqQueue &Q, QElemType e )
{//将元素e插入队尾
if ( (Q.rear+1)%MAXSIZE==Q.front )
return ERROR ; //队满
Q.base[Q.rear] = e ; //将元素e插入队尾Q.rear =
(Q.rear+1)%MAXSIZE; //修改队尾指针
return OK;
}//EnQueue
Status DeQueue( SqQueue &Q, QElemType &e )
{ //删除队头元素，用e返回其值，并返回OK；否则返回ERROR
if ( Q.rear==Q.front )
return ERROR ; //队空 e = Q.base[Q.front] ; // 取队头元素 e Q.front =
(Q.front+1)%MAXSIZE; //修改队头指针
return OK;
}//EnQueue
int CreateBiTree(BiTree &T)
{//按先序次序建立二叉链表表示的二叉树T
ElemType ch;
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); // 递归构造右子树链表
}
return OK;
}//CreateBiTree
void PreOrderTraverse( BiTree T)
{//先序遍历以T为根结点指针的二叉树
if (T) //若二叉树不为空
{ printf("%c",T->data); //访问根结点
PreOrderTraverse(T->lchild); //先序遍历T的左子树
PreOrderTraverse(T->rchild); //先序遍历T的右子树
}
} //PreOrderTraverse
void InOrderTraverse( BiTree T)
{//中序遍历以T为根结点指针的二叉树
if (T) //若二叉树不为空
{ InOrderTraverse(T->lchild); //中序遍历T的左子树 printf("%c",T->data); //访问根结点
InOrderTraverse(T->rchild); //中序遍历T的右子树
}
} //InOrderTraverse
void PostOrderTraverse( BiTree T)
{//后序遍历以T为根结点指针的二叉树
if (T) //若二叉树不为空
{ PostOrderTraverse(T->lchild); //后序遍历T的左子树
PostOrderTraverse(T->rchild); //后序遍历T的右子树
printf("%c",T->data); //访问根结点
}
} //PostOrderTraverse
void 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) EnQueue(q,p->lchild); //左子树进队列
if(p->rchild) EnQueue(q,p->rchild); //右子树进队列
}
}
四、程序调试分析
1.程序中用到的未定义的字符串要进行宏定义；
2.输入二叉树时要注意用空格代替子树为空；
3.二叉树的层次遍历可以借助队列来实现；
4.先定义二叉树，再定义队列元素的数据结构为二叉树类型，顺
