二叉树抽象大数据类型大数据结构实验报告材料.docx
《二叉树抽象大数据类型大数据结构实验报告材料.docx》由会员分享，可在线阅读，更多相关《二叉树抽象大数据类型大数据结构实验报告材料.docx（27页珍藏版）》请在冰点文库上搜索。
二叉树抽象大数据类型大数据结构实验报告材料
数据结构实验报告
题目：
二叉树抽象数据类型的实现
学院***学院
专业*********
年级班别***********
学号***********
学生姓名*************
指导教师
成绩____________________
2012年6月
报告：
内容：
□详细 □完整 □不完整
设计方案：
□非常合理 □合理 □较差
实现：
□全部实现 □部分实现 □未实现
文档格式：
□规范 □基本规范 □不规范
答辩：
□理解题目透彻，问题回答流利
□理解题目较透彻，回答问题基本正确
□部分理解题目，部分问题回答正确
□未能完全理解题目，答辩情况较差
总评成绩：
□优 □良 □中 □及格 □不及格
一．实验概要
二叉树抽象数据类型的实现
二.实验目的
1.了解二叉树的定义以及各项基本操作。
2.实现二叉树存储、遍历及其他基本功能
三.实验仪器设备和材料
Visualstudio2010
四．实验的内容
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，∈H，且存在Dr上的关系Hr∈H；H={，，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无右孩子或无右兄弟，则返回“空”。
}ADTBinaryTree
2.所选择的存储结构描述及在此存储结构上各基本操作的实现；
3.源代码
主文件:
main.ccp:
#include"base.h"//公用头文件、公共常量及公共函数等
#include"bitree.h"//二叉树二叉链表基本操作
voidMenu（）;//菜单函数
voidProduce（char*str）;//随机产生二叉树先序序列函数
intmain（）//主函数
{
BiTreeT,bt,insert_bt;
charcmd,str[MAXSIZE],elem;
intloc,temp;
InitBiTree（T）;//初始化二叉链表二叉树
Menu（）;//显示菜单
while
（1）
{
ClearLine（）;//清空结果显示区
printf（"请选择操作：
（按‘Q'退出）"）;
cmd=getch（）;
ClearLine（）;
fflush（stdin）;
switch（cmd）
{
case'0':
//随机创建一棵二叉树
while（cmd!
='y'&&cmd!
='Y'）
{
Produce（str）;//随机产生二叉树先序序列
CreateBiTree（T,str）;//用此序列建树
ShowBiTree（T）;//广义表形式显示
printf（"使用创建的这个二叉树?
"）;
cmd=getch（）;
ClearLine（）;
}
break;
case'2':
//手动创建一棵二叉树
printf（"请按二叉树先序序列输入二叉树：
（空结点用空格''表示）\n"）;
CreateBiTree（T）;
ClearLine（）;
printf（"二叉树创建成功!
\n"）;
ShowBiTree（T）;
getch（）;
break;
case'4':
//销毁二叉树
DestroyBiTree（T）;
printf（"二叉树已被销毁!
"）;
getch（）;
break;
case'6':
//判空
if（BiTreeEmpty（T））printf（"二叉树是空二叉树。
"）;
elseprintf（"二叉树非空"）;
getch（）;
break;
case'8':
//求深度
printf（"深度是%d",BiTreeDepth（T））;
getch（）;
break;
case'a':
//求左孩子
ShowBiTree（T）;
printf（"你想求哪个字符的左孩子？
"）;
do{
elem=getchar（）;
ClearLine（）;
bt=SearchBiTree（T,elem）;//查找指定的结点值elem
if（!
bt）printf（"你输入的结点不存在!
请重新输入：
"）;
}while（!
bt）;
ClearLine（）;
bt=LeftChild（T,bt）;//求左孩子
if（bt）printf（"%c的左孩子是%c",elem,bt->data）;
elseprintf（"%c没有左孩子",elem）;
printf（"\n参照二叉树:
"）;
ShowBiTree（T）;
getch（）;
break;
case'c':
//求右孩子
ShowBiTree（T）;
printf（"你想求哪个字符的右孩子？
"）;
do{
elem=getchar（）;
ClearLine（）;
bt=SearchBiTree（T,elem）;
if（!
bt）printf（"你输入的结点不存在!
请重新输入：
"）;
}while（!
bt）;
ClearLine（）;
bt=RightChild（T,bt）;
if（bt）printf（"%c的右孩子是%c",elem,bt->data）;
elseprintf（"%c没有右孩子",elem）;
printf（"\n参照二叉树:
"）;
ShowBiTree（T）;
getch（）;
break;
case'1':
//先序遍历
if（!
BiTreeEmpty（T））
{
printf（"先序遍历序列为：
"）;
PreOrderTraverse（T,Visit）;
}
elseprintf（"二叉树空，请先建树!
"）;
getch（）;
break;
case'3':
//中序遍历
if（!
BiTreeEmpty（T））
{
printf（"中序遍历序列为：
"）;
InOrderTraverse（T,Visit）;
}
elseprintf（"二叉树空，请先建树!
"）;
getch（）;
break;
case'5':
//后序遍历
if（!
BiTreeEmpty（T））
{
printf（"后序遍历序列为：
"）;
PostOrderTraverse（T,Visit）;
}
elseprintf（"二叉树空，请先建树!
"）;
getch（）;
break;
case'7':
//层次遍历
if（!
BiTreeEmpty（T））
{
printf（"层次遍历序列为：
"）;
LevelOrderTraverse（T,Visit）;
}
elseprintf（"二叉树空，请先建树!
"）;
getch（）;
break;
case'9':
//插入一棵二叉树为另一棵二叉树的子树
do{//随机创建一棵右孩子为空
Produce（str）;//且层数小于4的树
CreateBiTree（insert_bt,str）;
}while（insert_bt->rchild||BiTreeDepth（insert_bt）>3）;
printf（"先随机创建一棵右子树空的二叉树如图\n"）;
ShowBiTree（insert_bt）;//新创建的树
getch（）;
printf（"你想插入这棵树为原树哪个结点的子树:
\n"）;
ShowBiTree（T）;
bt=SearchBiTree（T,getchar（））;
ClearLine（）;
printf（"你想插入为0.左孩子1.右孩子:
"）;
fflush（stdin）;
scanf（"%d",&loc）;
if（!
InsertChild（T,bt,loc,insert_bt））
printf（"插入出错!
"）;
else{
ClearLine（）;
printf（"插入成功!
插入后T广义表形式为:
\n"）;
ShowBiTree（T）;
}
getch（）;
break;
case'b':
//删除指定结点的子树
ShowBiTree（T）;
printf（"你想删除哪个结点的子树?
"）;
fflush（stdin）;
bt=SearchBiTree（T,getchar（））;
printf（"\n你想删除0.左子树1.右子树:
"）;
fflush（stdin）;
scanf（"%d",&loc）;
ClearLine（）;
if（!
DeleteChild（T,bt,loc））printf（"删除出错!
"）;
elseprintf（"删除成功，检查结果\n"）;
ShowBiTree（T）;
getch（）;
break;
case'e':
//返回先序序列第i个结点的值
printf（"请输入一个结点的先序序列序号:
"）;
scanf（"%d",&loc）;
temp=loc;
ClearLine（）;
elem=Value（T,temp）;
printf（"参照二叉树:
"）;
ShowBiTree（T）;
printf（"\n"）;
if（elem==''）printf（"该结点不存在。
"）;
elseprintf（"先序序列第%d个结点值为%c",loc,elem）;
getch（）;break;
case'd':
//结点赋值
ShowBiTree（T）;
printf（"请输入要赋值的结点:
"）;
do{
elem=getchar（）;
ClearLine（）;
bt=SearchBiTree（T,elem）;
if（!
bt）printf（"你输入的结点不存在!
请重新输入：
"）;
}while（!
bt）;;
ClearLine（）;
printf（"请输入新值:
"）;
fflush（stdin）;
elem=getchar（）;
Assign（T,bt,elem）;
printf（"赋值成功，请查看二叉树状态.\n"）;
ShowBiTree（T）;
getch（）;
break;
case'Q':
//退出
case'q':
exit（0）;
}
}
return0;
}
voidMenu（）
//显示菜单函数
{
printf（"0.随机创建CreateBiTree（）1.先序遍历PreOrderTraverse（）"）;
printf（"\n\n2.手动创建CreateBiTree（）3.中序遍历InOrderTraverse（）"）;
printf（"\n\n4.销毁DestoryBiTree（）5.后序遍历PostOrderTraverse（）"）;
printf（"\n\n6.判空BiTreeEmpty（）7.层次遍历LevelOrderTraverse（）"）;
printf（"\n\n8.求深度BiTreeDepth（）9.插入子树InsertChild（）"）;
printf（"\n\na.求左孩子LeftChild（）b.删除子树DeleteChild（）"）;
printf（"\n\nc.求右孩子RightChild（）d.结点赋值Assign（）"）;
printf（"\n\ne.求结点值Value（）"）;
printf（"\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"）;
}
voidProduce（char*str）
//用随机数产生二叉树层次字符序列
//使所有节点的字符不相同，空节点用‘&’表示
{
intexist[27],i,elem,maxnodes=rand（）%41;
while（maxnodes<15||maxnodes>31）maxnodes=rand（）%41;
/*随机产生一个大于15小于31的随机数作为结点个数*/
for（i=0;i<27;i++）exist[i]=0;//初始化存在数组，用于使所有结点值不同
i=1;
while（i{
elem=rand（）%26;
if（!
exist[elem]&&str[i/2]!
='&'）//结点未生成且存在父节点
{
str[i++]=elem+'A';
exist[elem]=1;
}
elsestr[i++]='&';
}
str[i]='\0';
}
头文件:
base.h:
#include"stdio.h"
#include"conio.h"
#include"stdlib.h"
#include"windows.h"
#include"malloc.h"
#include"math.h"
#defineOK1
#defineTRUE1
#defineERROR0
#defineFALSE0
#defineMAXSIZE100
typedefintStatus;
typedefcharTElemType;
shortwherex（）//返回光标的x坐标
{
CONSOLE_SCREEN_BUFFER_INFOcsbinfo;
GetConsoleScreenBufferInfo（GetStdHandle（STD_OUTPUT_HANDLE）,&csbinfo）;
returncsbinfo.dwCursorPosition.X;
}
shortwherey（）//返回光标的y坐标
{
CONSOLE_SCREEN_BUFFER_INFOcsbinfo;
GetConsoleScreenBufferInfo（GetStdHandle（STD_OUTPUT_HANDLE）,&csbinfo）;
returncsbinfo.dwCursorPosition.Y;
}
voidgotoxy（shortx,shorty）//移动光标到（x，y）坐标
{
COORDpoint={x,y};
SetConsoleCursorPosition（GetStdHandle（STD_OUTPUT_HANDLE）,point）;
}
voidClearLine（unsignedy=17）
//清除第y行与y+1行的字符，并使光标在行首，默认清除第17至19行
{
for（inti=0;i<256;i++）
{
gotoxy（i,y）;
putchar（''）;
}
gotoxy（0,wherey（）-3）;
}
voidClearAera（unsignedx=96,unsignedy=17）
//清除（0,y）-（x,y+1）区域的字符，并使光标移动到y
{
for（unsignedi=0;i{
gotoxy（i%（x/2）,y+（i/48））;
putchar（''）;
}
gotoxy（0,y）;
}
StatusVisit（TElemTypee）
//二叉树结点visit函数，显示字符的值
{
printf（"%c",e）;
returnOK;
}
******************华丽的分割线***********************
bitree.h:
typedefcharTElemType;
typedefstructBiTNode
{
TElemTypedata;
structBiTNode*lchild;
structBiTNode*rchild;//左右孩子指针
}BiTNode,*BiTree;
voidInitBiTree（BiTree&T）
//构造空二叉树T
{
T=NULL;
}
StatusDestroyBiTree（BiTree&T）
//销毁二叉树T
{
if（!
T）returnERROR;
DestroyBiTree（T->lchild）;//删除左子树
DestroyBiTree（T->rchild）;//删除右子树
free（T）;
T=NULL;
returnOK;
}
StatusCreateBiTree（BiTree&T）
//先序建立二叉树T,空格表示空结点
{
TElemTypech;
fflush（stdin）;
ch=getche（）;
if（ch==''）T=NULL;
else{
T=（BiTree）malloc（sizeof（BiTNode））;
if（!
T）exit（OVERFLOW）;
T->data=ch;//生成头结点
CreateBiTree（T->lchild）;//构造左子树
CreateBiTree（T->rchild）;//构造右子树
}
returnOK;
}
StatusCreateBiTree（BiTree&T,char*str,unsignedi=1）
//str储存着二叉树的层次序列，str[i]=='&'表示结点不存在
//i为当前要创建结点对应的数组序号节点
//由字符数组str先序建立一棵二叉树T
{
if（str[i]=='&'||i>=strlen（str））T=NULL;//第i个结点不存在
else{
T=（BiTree）malloc（sizeof（BiTNode））;
if（!
T）exit（OVERFLOW）;
T->data=str[i];//生成根节点
CreateBiTree（T->lchild,str,i*2）;//构造左子树
CreateBiTree（T->rchild,str,i*2+1）;//构造右子树
}
returnOK;}
StatusBiTreeEmpty（BiTreeT）
//若T为空二叉树，则返回TRUE，否则返回FALSE
{
if（!
T）returnTRUE;
elsereturnFALSE;
}
intBiTreeDepth（BiTreeT）
//返回T的深度
//利用层次遍历求深度
升级会员 