广东工业大学数据结构二叉树课程设计.doc

数据结构实验报告
题目：二叉树抽象数据类型

学 院 计算机学院
专 业 计算机科学与技术
年级班别
学 号
学生姓名
指导教师

成 绩 ____________________

2013年6月

一．实验概要
实验项目名称: 二叉树抽象数据类型的实现
实验项目性质: 设计性实验
所属课程名称: 数据结构
实验计划学时: 6
二.实验目的
1. 了解二叉树的定义以及各项基本操作。
2. 实现二叉树存储、遍历及其他基本功能
三. 实验仪器设备和材料
硬件：PC机
软件：Visual C++ 6.0
四．实验的内容
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，<root，x1>∈H，且存在Dr上的关系Hr∈H；H={<root，x1>，<root，xr>，H1,Hr}；
(4) （D1，{H1}）是一棵符合本定义的二叉树，称为根的左子树，是一棵符合本定义的二叉树，称为根的右子树。
基本操作P:
InitBiTree(&T);
操作结果：构造空二叉树T。
DestroyBiTree(&T);
初始条件：二叉树T存在。
操作结果：销毁二叉树T。
CreateBiTree(&T,definition);
初始条件：definition给出二叉树T的定义。
操作结果：按definition构造二叉树T。
ClearBiTree(&T);
初始条件：二叉树T存在。
操作结果：将二叉树T清为空树。
BiTreeEmpty(T);
初始条件：二叉树T存在。
操作结果：若T为空二叉树，则返回TURE,否则FALSE。
BiTreeDepth(T);
初始条件：二叉树T存在。
操作结果：返回T的深度。
Root(T);
初始条件：二叉树T存在。
操作结果：返回T的根。
Value(T,e);
初始条件：二叉树T存在，e是T中的某个结点。
操作结果：返回e的值。
Assign(T,&e,value);
初始条件：二叉树T存在，e是T中的某个结点。
操作结果：结点e赋值为value。
Parent(T,e);
初始条件：二叉树T存在，e是T中的某个结点。
操作结果：若e是T的非跟结点，则返回它的双亲，否则返回“空”。
LeftChild(T,e);
初始条件：二叉树T存在，e是T中的某个结点。
操作结果：返回e的左孩子。若e无左孩子，则返回“空”。
RightChild(T,e);
初始条件：二叉树T存在，e是T中的某个结点。
操作结果：返回e的右孩子。若e无右孩子，则返回“空”。
LeftSibling(T,e);
初始条件：二叉树T存在，e是T中的某个结点。
操作结果：返回e的左兄弟。若e无左孩子或无左兄弟，则返回“空”。
RightSibling(T,e);
初始条件：二叉树T存在，e是T中的某个结点。
操作结果：返回e的右兄弟。若e无右孩子或无右兄弟，则返回“空”。
}ADT BinaryTree

2.存储结构：采用无头结点的链式存储结构实现
3.源代码：
头文件及存储结构:
#include<stdio.h>
#include<stdlib.h>

#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW 0
#define MAXQSIZE 100 //最大队列长度

typedef char TElemType;

typedef struct BiTNode //二叉树结构体
{
TElemType 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; //链队列结构体

算法设计：
int InitQueue(LinkQueue &Q) //构造空队列
{
Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));

if(!Q.front) //存储分配失败
exit(OVERFLOW);

Q.front->next = NULL;
return OK;
}

int EnQueue(LinkQueue &Q, QElemType e) //新元素入队尾
{
QueuePtr p;
p = (QueuePtr)malloc(sizeof(QNode));

if(!p) //存储分配失败
exit (OVERFLOW);

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

int DeQueue(LinkQueue &Q, QElemType &e) //删除队头元素
{
QueuePtr p;

if(Q.front == Q.rear) //队列为空队
return ERROR;

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

if(Q.rear == p) //判断删除队头元素后，队列是否为空队
Q.rear = Q.front;

free(p);
return OK;
}

int QueueEmpty(LinkQueue Q) //判断队列是否为空队
{
if (Q.front == Q.rear)
return TURE;
else
return FALSE;
}

int InitBiTree(BiTree &T) // 构造空二叉树
{
T = NULL;
return OK;
}

int DestroyTree(BiTree &T) //销毁二叉树
{
if(!T)
return ERROR;
else
DestroyTree(T->lchild);
DestroyTree(T->rchild);
free(T);
T=NULL;
return OK;
}

void CreateBiTree(BiTree &T) //用先序遍历的方式构建二叉树,以‘@’表示空结点。
{
TElemType ch;
scanf("%c",&ch);
if(ch=='@')
T=NULL;
else
{
if(!(T=(BiTree)malloc(sizeof(BiTNode))))
exit(OVERFLOW); //分配存储空间失败
T->data=ch;
CreateBiTree(T->lchild); //构造左子树
CreateBiTree(T->rchild); //构造右子树
}
}

int ClearBiTree(BiTree &T) //清空二叉树函数
{
if(!T)
return ERROR;
else
{
ClearBiTree(T->lchild);
ClearBiTree(T->rchild);
free(T);
T=NULL;
return OK;
}
}

int BiTreeEmpty(BiTree T) //判断二叉树是否为空
{
if(!T)
return TURE;
else
return FALSE;
}

int BiTreeDepth(BiTree T) //计算二叉树深度
{
int lcd,rcd;
if(!T)
return 0;
lcd=BiTreeDepth(T->lchild);
rcd=BiTreeDepth(T->rchild);
return ((lcd>rcd?lcd:rcd)+1);
}

TElemType Root(BiTree T) //判断二叉树是否空，若非空返回其根
{
if(BiTreeEmpty(T))
return NULL;
else
return (T->data);
}

TElemType Value(BiTree T,BiTree e) //返回e结点的值
{
return e->data;
}

int Assign(BiTree T,BiTree &e,TElemType value) // 将value的值给结点e
{
e->data=value;
return OK;
}

TElemType Parent(BiTree T,TElemType e)
{//返回双亲
LinkQueue q;
QElemType a;
if(T)
{
InitQueue(q);
EnQueue(q,T);//树根入队列
while(!QueueEmpty(q))//队不空
{
DeQueue (q, a);//出队，队列元素赋给a
if(a->lchild&&a->lchild->data==e||a->rchild&&a->rchild->data==e) //找到e
return a->data; //返回双亲的值
else
{
if(a->lchild)
EnQueue(q,a->lchild);//入队列左孩子
if(a->rchild)
EnQueue(q,a->rchild);//入队列右孩子
}
}
}
return NULL;
}

BiTree Point(BiTree T,TElemType s)//返回二叉树T中指向元素值为S的结点指针
{
LinkQueue q;
QElemType a;
if(T)
{
InitQueue(q);
EnQueue(q,T);
while(!QueueEmpty(q))
{
DeQueue(q,a);
if(a->data==s)
{
return a;
}
if(a->lchild)
{
EnQueue(q,a->lchild);
}
if(a->rchild)
{
EnQueue(q,a->rchild);
}
}
}
return NULL;

}

TElemType LeftChild(BiTree T,TElemType e)
{//返回e的左孩子
BiTree a;
if(T)
{
a=Point(T,e);//a是指向结点e的指针
if(a&&a->lchild)
return a->lchild->data;
}
return NULL;
}

TElemType RightChild(BiTree T,TElemType e) //返回e的右孩子
{
BiTree a;
if(T)
{
if((a=Point(T,e))&&a->rchild)
return a->rchild->data;
}
return NULL;
}

TElemType LeftSibling(BiTree T,TElemType e)
{ //返回左兄弟
TElemType a;
BiTree p;
if(T)
{
a=Parent(T,e);//a为e的双亲
if(a!=NULL)
{
p=Point(T,a);//p指向结点a的指针
if(p->lchild&&p->rchild&&p->rchild->data==e)//p存在左右孩子而且右孩子是e
return p->lchild->data;
}
}
return NULL;
}

TElemType RightSibling(BiTree T,TElemType e)
{ //返回右兄弟
TElemType a;
BiTree p;
if(T)
{
a=Parent(T,e);//a为e的双亲
if(a!=NULL)
{
p=Point(T,a);//p指向结点a的指针
if(p->lchild&&p->rchild&&p->lchild->data==e)//p存在左右孩子而且左孩子是e
return p->rchild->data;
}
}
return NULL;
}

int InsertChild(BiTree T,BiTree p,int LR,BiTree c) //根据LR为0或者1，插入C为T中P所指结点的左或者右子树，
//P所指的结点原有左或右子树则成为C的右子树
{
if(p)
{
if(LR==0) //把二叉树C插入p所指结点的左子树
{
c->rchild=p->lchild;
p->lchild=c;
}
else
{
c->rchild=p->rchild;
p->rchild=c;
}
return OK;
}
return ERROR;
}

int DeleteChild(BiTree T,BiTree p,int LR)
{
if(p)
{
if(LR==0)
{
ClearBiTree(p->lchild);
}
else
{
ClearBiTree(p->rchild);
}
return OK;
}
return ERROR;
}

void visit(TElemType e) //二叉树结点访问函数
{
printf("%c",e);
}

int PreOrderTraverse(BiTree T,void(*visit)(TElemType)) //先序遍历二叉树
{
if(T)
{
visit(T->data);
PreOrderTraverse(T->lchild,visit);
PreOrderTraverse(T->rchild,visit);
return OK;
}
return ERROR;
}

int InOrderTraverse(BiTree T,void(*visit)(TElemType))
{ //中序遍历二叉树
if(T)
{
InOrderTraverse(T->lchild,visit);
visit(T->data);
InOrderTraverse(T->rchild,visit);
return OK;
}
return ERROR;
}

int PostOrderTraverse(BiTree T,void(*visit)(TElemType))
{ //后序遍历二叉树
if(T)
{
PostOrderTraverse(T->lchild,visit);
PostOrderTraverse(T->rchild,visit);
visit(T->data);
return OK;
}
return ERROR;
}

int LevelOrderTraverse(BiTree T,void(*visit)(TElemType))
{//层序遍历二叉树
LinkQueue q;
QElemType a;
if(T)
{
InitQueue(q);//初始化队列
EnQueue(q,T);//根指针入队
while(!QueueEmpty(q))
{
DeQueue(q,a);//出队元素，赋给a
visit(a->data);//访问a所指结点
if(a->lchild!=NULL)
EnQueue(q,a->lchild);
if(a->rchild!=NULL)
EnQueue(q,a->rchild);
}
return OK;
}
return ERROR;
}

主函数：
int main()
{
int i,j,LR;
TElemType value,a,temp;
BiTree p,C;
printf("欢迎使用本二叉树程序，请按回车键继续...\n");
getchar();
printf("正在构造空二叉树，请稍候...");
printf("\n");
BiTree T;
InitBiTree(T);
if(BiTreeEmpty(T))
printf("构造空二叉树成功！\n");
else
printf("构造空二叉树失败！\n");
printf("请按先序遍历顺序输入二叉树各结点的值！空结点用@表示！\n");
CreateBiTree(T);
printf("\n");
getchar();
printf("请选择接下来的操作:输入“1”为查看二叉树深度，输入“2”为查看二叉树根节点...\n");
scanf("%d",&i);
if(i==1)
printf("此二叉树的深度为：%d\n\n",BiTreeDepth(T));
if(i==2)
printf("此二叉树的根节点为：%c\n\n",Root(T));
printf("请选择遍历该二叉树的顺序：输入“1”为先序遍历，输入“2”为中序遍历，输入“3”为后序遍历，输入“4”为层序遍历...\n");
scanf("%d",&i);
getchar();
printf("\n");
if(i==1)
{
j=PreOrderTraverse(T,visit);
printf("\n");
if(j==0)
printf("该二叉树为空树，请重新运行程序！\n");
}
if(i==2)
{
j=InOrderTraverse(T,visit);
printf("\n");
if(j==0)
printf("该二叉树为空树，请重新运行程序！\n");
}
if(i==3)
{
j=PostOrderTraverse(T,visit);
printf("\n");
if(j==0)
printf("该二叉树为空树，请重新运行程序！\n");
}
if(i==4)
{
j=LevelOrderTraverse(T,visit);
printf("\n");
if(j==0)
printf("该二叉树为空树，请重新运行程序！\n");
}
printf("\n请输入需要替换的结点：\n");
scanf("%c",&a);
getchar();
p=Point(T,a);
printf("请输入需要代入的结点值：\n");
scanf("%c",&value);
getchar();
Assign(T,p,value);
printf("赋值之后该结点的值为：%c\n\n",p->data);
printf("请输入“1”求该结点的双亲结点，输入“2”求该结点的左孩子，输入“3”求该结点的右孩子，输入“4”求该结点的左兄弟，输入“5”求该结点的右兄弟..\n\n");
scanf("%d",&i);
getchar();
switch(i)
{
case 1:
{
if(Parent(T,value)==NULL)
printf("该结点没有双亲结点。\n");
else
printf("该结点的双亲结点为：%c\n\n",Parent(T,value));break;
}
case 2:
{
if(LeftChild(T,value)==NULL)
printf("该结点没有左孩子结点。\n");
else
printf("该结点的左孩子结点为：%c\n\n",LeftChild(T,value));break;

}
case 3:
{
if(RightChild(T,value)==NULL)
printf("该结点没有右孩子结点。\n");
else
printf("该结点的右孩子结点为：%c\n\n",RightChild(T,value));break;
}
case 4:
{
if(LeftSibling(T,value)==NULL)
printf("该结点没有左兄弟。\n");
else
printf("该结点的左兄弟为：%c\n\n",LeftSibling(T,value));
break;
}
case 5:
{
if(RightSibling(T,value)==NULL)
printf("该结点没有右兄弟。\n");
else
printf("该结点的右兄弟为：%c\n\n",RightSibling(T,value));
break;
}
}
printf("\n现在进行结点插入子树，请按照先序遍历的顺序输入二叉树C，注意该二叉树没有右子树！\n");
InitBiTree(C);
CreateBiTree(C);
getchar();
printf("\n请输入您需要插入子树的结点：\n");
scanf("%c",&a);
getchar();
p=Point(T,a);
printf("\n输入0示插入C为%c结点的左子树而该结点原来的左子树变为c的右子树...",a);
printf("\n输入1示插入C为%c结点的右子树而该结点原来的左子树变为c的右子树,请选择...\n",a);
scanf("%d", &LR);
getchar();
j= InsertChild(T, p, LR, C);
if(j==0)
{
printf("插入失败！\n");
}
else
{
printf("插入成功！该新二叉树的先序遍历为：");
PreOrderTraverse(T, visit);
}
printf("\n\n进行删除操作，请输入需要删除左子树或者右子树的结点：");
scanf("%c",&a);
getchar();
p=Point(T,a);
printf("\n输入 0 表示删除%c结点的左子树， 1 表示删除%c结点的右子树，请选择...\n",a);
scanf("%d", &LR);
getchar();
j = DeleteChild(T, p, LR);
if(j==0)
{
printf("删除失败！\n");
}
else
{
printf("删除成功！该新二叉树的先序遍历为：");
PreOrderTraverse(T, visit);
}
DestroyTree(T);
if (!T)
printf("\n树已被成功销毁！程序执行完毕，请按回车键\n");
else
printf("\n树销毁不成功！程序执行完毕，请按回车键\n");
getchar();
for(i=1;i<=4;++i)
printf("\n");
printf(" ***************************************************************************\n");
printf(" ***************************************************************************\n");
printf(" ***************************************************************************\n");
printf(" ***************************************************************************\n");
printf(" ***************************************************************************\n");
printf(" ***************************************************************************\n");
printf(" ***************************************************************************\n");
printf(" ***************************************************************************\n");
printf(" ****************************** 感谢使用 *****************************\n");
printf(" ****************************** * * *****************************\n");
printf(" ****************************** 计科四班 *****************************\n");
printf(" ****************************** *****************************\n");
printf(" ******************************制作人：罗志权 *****************************\n");
printf(" ****************************** *****************************\n");
printf(" ******************************学号：3111005843*****************************\n");
printf(" ***************************** *****************************\n");
printf(" *****************************请按回车键退出程序****************************\n");
printf(" ***************************************************************************\n");
printf(" ***************************************************************************\n");
printf(" ***************************************************************************\n");
printf(" ***************************************************************************\n");
printf(" ***************************************************************************\n");
printf(" ***************************************************************************\n");

getchar();

return OK;
}

4.程序清单（计算机打印），输入的数据及各基本操作的测试结果；
開始：

第一步：手动创建二叉树：

第二步：选择操作，这里选择查看深度：

第三步：选择遍历方法，这里选择中序遍历：

第五步：替换某个结点：

第六步：求该结点的邻近结点，这里选择右孩子：

第七步：插入子树C到e结点作为e结点的左子树：

第八步：删除结点的左子树或者右子树：

程序执行完毕：

显示作者：

六.实验总结和体会。
抽象数据类型是模块化思想的发展，有助于我们从更抽象的高度去讨论算法和数据结构的问题。通过这次实验，我对二叉树的抽象数据类型更加了解和熟悉，我们只需关心它的逻辑特征而不需要了解它的存储方式。数据结构是每个程序员的必修课，但是我们还要学的还有很多很多，因为在设计程序的时候会遇到很多的BUG，这些BUG都是要靠自己慢慢去了解慢慢去调试才能解决的。而且现在计算机技术发展迅速，我们要学的可以说是无穷无尽的。

THANKS !!!

致力为企业和个人提供合同协议，策划案计划书，学习课件等等
打造全网一站式需求

欢迎您的下载，资料仅供参考