北理工数据结构实验报告3

《数据结构与算法设计》

实验报告

——实验三

学院：自动化学院 班级：___ 学号：__ 姓名：____ ___

一、实验目的

1、熟悉VC环境，学习使用C语言实现二叉树的存储结构。

2、通过编程、上机调试，进一步二叉树、队列的基本概念。 3、锻炼动手编程，思考的能力。 二、实验内容

遍历二叉树：请输入一棵二叉树的扩展的前序序列，经过处理后生成一棵二叉树，然后对于该二叉树输出前序、中序、后序和层次遍历序列。 三、程序设计 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})

是一棵符合本定义的二叉树，称为根的右子树。

基本操作：

InitBiTree( &T )

操作结果：构造空二叉树T。 CreateBiTree( &T, definition )

初始条件：definition给出二叉树T的定义。 操作结果：按definiton构造二叉树T。 PreOrderTraverse( T, visit() )

初始条件：二叉树T存在，Visit是对结点操作的应用函数。

操作结果：先序遍历T，对每个结点调用函数Visit一次且仅一次。一

旦visit()失败，则操作失败。

InOrderTraverse( T, visit() )

初始条件：二叉树T存在，Visit是对结点操作的应用函数。

操作结果：中序遍历T，对每个结点调用函数Visit一次且仅一次。一

旦visit()失败，则操作失败。

PostOrderTraverse( T, visit() )

初始条件：二叉树T存在，Visit是对结点操作的应用函数。

操作结果：后序遍历T，对每个结点调用函数Visit一次且仅一次。一

旦visit()失败，则操作失败。

LevelOrderTraverse( T, visit() )

初始条件：二叉树T存在，Visit是对结点操作的应用函数。

操作结果：层次遍历T，对每个结点调用函数Visit一次且仅一次。一

旦visit()失败，则操作失败。

}ADT BinaryTree (2)、宏定义

#define OVERFLOW -2 #define OK 1

#define ERROR 0 (3)、主程序流程

主程序首先调用CreateBiTree(BIT)函数通过拓展的前序序列创建二叉树BIT，随后按照顺序分别调用四个函数，即：PreOrderTraverse(BIT)、InOrderTraverse(BIT)、 PostOrderTraverse(BIT)与LevelOrderTraverse(BIT)函数计算并输出二叉树的前序、中序、后序以及层次遍历序列。 (4)、模块调用关系：

由主函数模块调用创建模块，与计算模块。由计算模块将结果输出。 (5)、流程图

主程序流程图： 开始

创建二叉树

计算并输 出结果

结束

前序遍历流程图；

中序、后序与前序类似。 2、详细设计

(1)、数据类型设计 typedef int Status;

typedef char ElemType; //定义二叉树元素类型 typedef struct BiTNode{ ElemType data;

struct BiTNode *lchild,*rchild;

}BiTNode,*BiTree; //定义二叉树数据类型 typedef BiTree QElemType; //定义队列元素类型 typedef struct QNode{ QElemType data; struct QNode *next;

}QNode,*QueuePtr; //定义队列结点 typedef struct{ QueuePtr front; QueuePtr rear;

}LinkQueue; //定义队列数据类型 (2)、操作算法设计

Status InitQueue(LinkQueue &Q){ //创建队列

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front)exit(OVERFLOW); //存储分配失败 Q.front->next=NULL; return OK; }

Status EnQueue(LinkQueue &Q,QElemType e){ //插入元素e作为新的队尾元素

QNode *p=(QueuePtr)malloc(sizeof(QNode)); if(!p)exit(OVERFLOW); //存储分配失败 p->data=e;

p->next=NULL; Q.rear->next=p; Q.rear=p; return OK; }

Status DeQueue(LinkQueue &Q,QElemType &e){ //删除队头元素并以e返回

if(Q.front==Q.rear)return ERROR; QNode *p=Q.front->next; e=p->data;

Q.front->next=p->next;

if(Q.rear==p)Q.rear=Q.front; free(p);

return OK; }

Status CreateBiTree(BiTree &T){ //创建二叉树 char ch;

scanf(\"%c\ if(ch==' ')T=NULL; else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))exit(OVERFLOW); T->data=ch; //生成根结点 CreateBiTree(T->lchild); //构造左子树 CreateBiTree(T->rchild); //构造右子树 }

return OK; }

Status LevelOrderTraverse(BiTree &T){ //层次遍历

QElemType p; LinkQueue q; InitQueue(q);

if(T) EnQueue(q,T); //队头元素进队列 while(!(q.front==q.rear)){ DeQueue(q,p); printf(\"%c\输出队头元素 if(p->lchild) EnQueue(q,p->lchild); //左子树进队列 if(p->rchild) EnQueue(q,p->rchild); //右子树进队列 }

return OK; }

void InOrderTraverse(BiTree T){ //中序遍历 if(T){ InOrderTraverse(T->lchild); printf(\"%c\ InOrderTraverse(T->rchild); } }

void PostOrderTraverse(BiTree T){ //后续遍历 if(T){ PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); printf(\"%c\ }

}

void PreOrderTraverse(BiTree T){ //前序遍历 if(T){ printf(\"%c\ PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } }

(3)、主函数设计 int main(){ //主程序

BiTNode* BIT;

printf(\"Please input the binary tree:\\n\"); CreateBiTree(BIT); //创建二叉树BIT

printf(\"The result of PreOrderTraverse is:\\n\"); PreOrderTraverse(BIT); //前序 printf(\"\\n\");

printf(\"The result of InOrderTraverse is:\\n\"); InOrderTraverse(BIT); //中序 printf(\"\\n\");

printf(\"The result of PostOrderTraverse is:\\n\"); PostOrderTraverse(BIT); //后序 printf(\"\\n\");

printf(\"The result of LevelOrderTraverse is:\\n\"); LevelOrderTraverse(BIT); //层次 printf(\"\\n\"); return 0; }

四、程序调试分析

1、开始时曾忽略了一些函数形参的引用标识符&，在调试时浪费了不少时间。今后应多注意细节并仔细确定函数形参的类型。

2、在定义队列时，数据元素类型搞混，没有定义为二叉树类型，导致编译通过但是结果错误。经过仔细检查后改正了这一错误。

3、层次遍历中，指针类型与数据类型混淆，导致编译失败。这是一个比较严重的错误，以后一定要加以注意。 五、用户使用说明

1、本程序的运行环境为DOS操作系统，执行文件为：Traverse.exe。 2、进入程序后，在Please input the binary tree:后按照拓展的前序序列（即空子树处输入空格）输入二叉树，回车后程序即运行。

3、程序运行后即在屏幕上输出计算结果。 六、程序运行结果

1、

2、

七、程序清单

#define OVERFLOW -2 #define OK 1 #define ERROR 0 #include\"stdio.h\" #include\"stdlib.h\" typedef int Status;

typedef char ElemType; //定义二叉树元素类型 typedef struct BiTNode{ ElemType data;

struct BiTNode *lchild,*rchild;

}BiTNode,*BiTree; //定义二叉树数据类型 typedef BiTree QElemType; //定义队列元素类型 typedef struct QNode{ QElemType data; struct QNode *next;

}QNode,*QueuePtr; //定义队列结点 typedef struct{ QueuePtr front; QueuePtr rear;

}LinkQueue; //定义队列数据类型 Status InitQueue(LinkQueue &Q){ //创建队列

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front)exit(OVERFLOW); //存储分配失败 Q.front->next=NULL;

return OK; }

Status EnQueue(LinkQueue &Q,QElemType e){ //插入元素e作为新的队尾元素

QNode *p=(QueuePtr)malloc(sizeof(QNode)); if(!p)exit(OVERFLOW); //存储分配失败 p->data=e;p->next=NULL; Q.rear->next=p; Q.rear=p; return OK; }

Status DeQueue(LinkQueue &Q,QElemType &e){ //删除队头元素并以e返回

if(Q.front==Q.rear)return ERROR; QNode *p=Q.front->next; e=p->data;

Q.front->next=p->next;

if(Q.rear==p)Q.rear=Q.front; free(p); return OK; }

Status CreateBiTree(BiTree &T){ //创建二叉树 char ch;

scanf(\"%c\ if(ch==' ')T=NULL; else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))exit(OVERFLOW); T->data=ch; //生成根结点 CreateBiTree(T->lchild); //构造左子树 CreateBiTree(T->rchild); //构造右子树 }

return OK; }

Status LevelOrderTraverse(BiTree &T){ //层次遍历

QElemType p; LinkQueue q; InitQueue(q); if(T) EnQueue(q,T); //队头元素进队列 while(!(q.front==q.rear)){ DeQueue(q,p); printf(\"%c\输出队头元素 if(p->lchild) EnQueue(q,p->lchild); //左子树进队列 if(p->rchild) EnQueue(q,p->rchild); //右子树进队列 }

return OK; }

void InOrderTraverse(BiTree T){ //中序遍历 if(T){ InOrderTraverse(T->lchild); printf(\"%c\ InOrderTraverse(T->rchild); } }

void PostOrderTraverse(BiTree T){ //后续遍历 if(T){ PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); printf(\"%c\ } }

void PreOrderTraverse(BiTree T){ //前序遍历 if(T){ printf(\"%c\ PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } }

int main(){ //主程序

BiTNode* BIT;

printf(\"Please input the binary tree:\\n\"); CreateBiTree(BIT); //创建二叉树BIT

printf(\"The result of PreOrderTraverse is:\\n\"); PreOrderTraverse(BIT); //前序 printf(\"\\n\");

printf(\"The result of InOrderTraverse is:\\n\"); InOrderTraverse(BIT); //中序 printf(\"\\n\");

printf(\"The result of PostOrderTraverse is:\\n\"); PostOrderTraverse(BIT); //后序 printf(\"\\n\");

printf(\"The result of LevelOrderTraverse is:\\n\"); LevelOrderTraverse(BIT); //层次 printf(\"\\n\"); return 0;}