数据结构实验三二叉树基本操作及运算实验报告Word格式.docx
- 文档编号:1293072
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:45
- 大小:145.22KB
数据结构实验三二叉树基本操作及运算实验报告Word格式.docx
《数据结构实验三二叉树基本操作及运算实验报告Word格式.docx》由会员分享,可在线阅读,更多相关《数据结构实验三二叉树基本操作及运算实验报告Word格式.docx(45页珍藏版)》请在冰点文库上搜索。
删除B后,以广义表形式打印A(,C(F(,G)))
二、概要设计
程序中将涉及下列两个抽象数据类型:
一个是二叉树,一个是队列。
1、设定“二叉树”的抽象数据类型定义:
ADTBiTree{
数据对象D:
D是具有相同特性的数据元素的集合。
数据关系R:
若
,则
,称BiTree为空二叉树;
,H是如下二元关系:
(1)在D中存在唯一的称为根的数据元素root,它在关系H下无前驱;
(2)若
则存在
且
;
(3)若
则
中存在唯一的元素
且存在
上的关系
若
;
(4)
是一棵符合本定义的二叉树,称为根的左子树,
是一棵符合本定义的二叉树,称为根的有字树
基本操作:
CreateBiTree&
T)
操作结果:
按照T的定义构造一个二叉树。
BiTreeDepth(&
T)
初始条件:
二叉树T已存在。
返回T的深度。
BiTreeWidth(&
初始条件:
返回T的宽度。
PreOderTraverse&
先序遍历打印T,
InOderTraverse(&
中序遍历打印T。
PostOderTraverse(&
后序遍历打印T。
LevelTraverse(&
层次遍历T。
DeleteXTree(&
T,TElemTypex)
二叉树已存在。
删除元素为x的结点以及其左子树和右子树。
CopyTree(&
以T为模板,复制另一个二叉树。
}ADTBiTree
2、设定队列的抽象数据类型定义:
ADTQueue{
数据对象:
D={
数据关系:
R1={<
>
|
i=2,…,n}
约定
端为队列头,
端为队列尾。
InitQueue(&
Q)
构造一个空队列Q。
EnQueue(&
Q,&
e)
队列Q已存在。
插入元素e为Q的新的队尾元素。
DeQueue(&
删除Q的对头元素,并返回其值。
QueueEmpty(&
若Q为空队列,则返回1,否则0。
}ADTQueue
3、本程序包含四个模块
1)主程序模块
voidmain()
{
初始化;
先序输入二叉树各结点元素;
各种遍历二叉树;
对二叉树进行常见运算;
复制二叉树;
在复制的二叉树上进行二叉树的常见操作;
}
2)二叉树模块——实现二叉树的抽象数据类型和基本操作
2)队列模块——实现队列的抽象数据类型及今本操作
3)广义表打印模块——以广义表形式打印二叉树
4)二叉树运算模块——对二叉树的叶子、非空子孙结点数目、度为2或1的结点数
三、详细设计
1、主程序中需要的全程量
#defineM10//统计二叉树宽度时需用数组对每层宽度进行存储,这M表示数组的长度
2、队列的建立与基本操作
typedefstructQNode{
BiTreedata;
//队列中存储的元素类型
structQNode*next;
//指向二叉树结点的指针
}QNode,*Queueptr;
typedefstruct{
Queueptrfront;
//队列的队头指针
Queueptrrear;
//队列的队尾指针
}LinkQueue;
算法描述:
为了对二叉树进行层次遍历,需要“先访问的结点,其孩子结点必然也先访问”,故需运用到队列。
而考虑到层次遍历对队列操作的需要,只需进行队列的初始化,入队和出队以及检查队列是否为空。
伪码算法:
voidInitQueue(LinkQueue*Q)
{//初始化队列申请一个结点
Q->
front=Q->
rear=(Queueptr)malloc(sizeof(QNode));
if(!
Q->
front)
exit
(1);
//存储分配失败处理
front->
next=NULL;
//构成带头结点里的空链队列
}
voidEnQueue(LinkQueue*Q,BiTreee)
{//插入元素为e为Q的队尾元素
Queueptrq;
q=(Queueptr)malloc(sizeof(QNode));
q)
q->
data=e;
rear->
next=q;
//元素e的结点入列
rear=q;
BiTreeDeQueue(LinkQueue*Q)
{//从队列中删除队头元素,并直接返回给调用的主函数
Queueptrp;
BiTreeq;
if(Q->
front==Q->
rear)
{//队列为空
printf("
ERROR!
\n"
);
}
p=Q->
next;
q=p->
data;
next=p->
//删除该结点
rear==p)
Q->
rear=Q->
front;
free(p);
returnq;
//返回队头元素
intQueueEmpty(LinkQueue*Q)
{//检查队列是否为空,若为空则返回真值,否则返回0
return1;
else
return0;
3、二叉树的建立与基本操作
typedefstructBiTNode{
TElemTypedata;
//二叉树结点存储的元素类型
structBiTNode*lchild,*rchild;
//二叉树左右孩子指针
}BiTNode,*BiTree;
算法分析:
二叉树的基本操作是本程序的核心,考虑到二叉树的定义就是采用递归定义,所以很容易想到对二叉树的操作可通过递归调用来实现。
1)二叉树的遍历
二叉树中常常要求在树中查找具有某种特征的结点,或者对树中全部结点逐一进行某种处理,这就需要遍历二叉树。
即要求按某条路径寻访树中的每个结点,使得每个结点均被访问一次,而且仅被访问一次。
回顾二叉树的递归定义可知,二叉树是由3个基本单元组成:
根节点、左子树和右子树。
因此,若能依次遍历这三部分,便是遍历了整棵二叉树。
如果以L、D、R分别表示遍历左子树、访问根结点和遍历右子树,则可有DLR、LDR、LRD、DRL、RDL、RLD这6种遍历二叉树的方案。
若限定先右后左,则只有前三种情况,分别称之为先(根)序遍历。
中(根)序遍历和后(根)序遍历。
基于二叉树的递归定义,可得下述遍历二叉树的递归定义算法。
先序遍历二叉树的操作定义:
若二叉树为空,则空操作;
否则
(1)访问根结点;
(2)先序遍历左子树;
(3)先序遍历右子树。
voidPreOderTraverse(BiTreeT)
{//采用二叉链表存储结构
if(T)
{
putchar(T->
data);
//最简单的访问结点法,输出结点元素,这里先访问根结点
PreOderTraverse(T->
lchild);
rchild);
中序遍历二叉树的操作定义:
(1)中序遍历左子树;
(2)访问根结点;
(3)中序遍历右子树。
voidInOderTraverse(BiTreeT)
InOderTraverse(T->
//先遍历左子树
//最简单的访问结点法,输出结点元素,这里第二访问根结点
}
后序遍历二叉树的操作定义:
(1)后序遍历左子树;
(2)后序遍历右子树;
(3)访问根结点。
voidPostOderTraverse(BiTreeT)
PostOderTraverse(T->
//再遍历右子树
putchar(T->
//最后访问根结点
2)二叉树的建立
对二叉树“遍历”基本操作已经建立的基础上,可以在便利过程中对结点进行各种操作,如:
在遍历过程中生成结点,建立二叉树存储结构。
采用先序遍历建立二叉树链表:
(1)按先序序列输入二叉树中结点的元素,以空格表示空,直到输入回车为止;
(2)若元素值为空,则赋值NULL;
否则生成一个新的结点,将元素值赋值给该跟结点的数值域;
(3)建立该跟结点的左子树;
(4)建立该根结点的右子树。
伪码算法;
BiTreeCreateBiTree(BiTreeT)
{//构造二叉树T,按先序序列输入二叉树中结点的值(一个字符),空格表示空树
charch;
if((ch=getchar())=='
'
)
T=NULL;
if(ch!
='
\n'
if(!
(T=(BiTree)malloc(sizeof(BiTNode))))
T->
data=ch;
//生成根结点
lchild=CreateBiTree(T->
//构造左子树
rchild=CreateBiTree(T->
//构造右子树
}
returnT;
//返回所构造二叉树(子)树的地址
3)二叉树的层次遍历
有时需要一层层访问二叉树,比如判断二叉树是否为完全二叉树、找出指定层中含有的叶子/度为2/度为1的结点等,这就需要另一种遍历方法——层次遍历。
先访问的结点,其孩子结点必然也先访问,引入队列存储已被访问的,但其左右孩子尚未访问的结点的指针。
算法描述:
(1)若结点不为空,则访问该结点,并将其入列;
(2)接着从队列中取已被访问的,但其左右孩子尚未被访问的;
(3)访问该结点的左孩子,将其入列;
(4)访问该结点的右孩子,将其入列。
intvisit(TElemTypee)
{//简单的结点访问函数
if(e)
putchar(e);
//打印该结点元素
voidLevelTraverse(BiTreeT)
LinkQueue*Q=(LinkQueue*)malloc(sizeof(LinkQueue));
BiTreep=(BiTree)malloc(sizeof(BiTNode));
InitQueue(Q);
//初始化队列,队列的元素为二叉树的结点指针
if(T!
=NULL)
visit(T->
data))//访问该结点
exit
(1);
EnQueue(Q,T);
//将已被访问的,但左右孩子没被访问的结点入列
while(!
QueueEmpty(Q))
{//队列不为空,则尚有未被访问其孩子的结点
p=DeQueue(Q);
//将该结点出列,返回其地址
if(p->
lchild!
{
if(!
visit(p->
lchild->
data))//访问左孩子
exit
(1);
EnQueue(Q,p->
//将其入列
rchild!
rchild->
data))//访问右孩子
4)求二叉树的深度
(1)若结点不为空,则求其左子树的深度,并返回其值h1;
(2)求其右子树的深度,也返回其值h2;
(3)选择左右子树深度的最大值,将其加一(该结点本身深度)即为该结点子树的深度。
intBiTreeDepth(BiTreeT)
{//后序遍历求树T所指二叉树的深度
inthl=0,hr=0;
hl=BiTreeDepth(T->
//求左子树的深度
hr=BiTreeDepth(T->
//求右子树的深度
if(hl>
=hr)returnhl+1;
elsereturnhr+1;
//子树深度的最大值再加上本身所在结点的深度记为子树的深度
5)求二叉树的宽度
(1)定义一个数组,来存放每层的结点数,max来存放到这层为止时的最大结点数;
(2)计算每一层的结点数将其赋值给对应的数组元素;
(3)每层计算完后,用max与本层结点数比较,若max小,则将本层结点数赋值给max;
(4)最后返回max。
intBiTreeWidth(BiTreeT,inti)
intstaticn[M]={0};
//存放各层结点数,M为最先预料的最大树的最大深度
intstaticmax=0;
//最大宽度
if(i==1)//若是访问根结点
{
n[i]++;
//第一层加1
i++;
//到第二层
if(T->
lchild)
n[i]++;
//若有左孩子则该层加1
rchild)
//若有右孩子则该层加1
else
{//访问子树的结点
//向下一层
if(max<
n[i])
max=n[i];
//取出目前为止,各层结点数的最大值
BiTreeWidth(T->
lchild,i);
//遍历左子树
rchild,i--);
//网上退一层后遍历右子树
returnmax;
6)删除二叉树的某个结点
(1)先序遍历找到该结点;
(2)若此结点为空,不必释放;
若不为空,则先释放其左右子树的所有结点的空间,再赋为空;
(3)再释放根结点的空间,并将这个结点的父节点指向该结点的指针域赋为空。
BiTreeDeleteBiTree(BiTreet)
{//释放该结点空间的函数
if(t!
t->
lchild=DeleteBiTree(t->
//释放其左子树的空间
rchild=DeleteBiTree(t->
//释放右子树的空间
free(t);
//释放根结点的空间
t=NULL;
//将其值赋为空
returnt;
BiTreeDeleteXTree(BiTreet,TElemTypex)
{//先序查找到需删结点位置
if(t->
data==x){//判断是否为指定结点
DeleteBiTree(t);
//释放树的空间
t=NULL;
t->
lchild=DeleteXTree(t->
lchild,x);
rchild=DeleteXTree(t->
rchild,x);
7)复制二叉树
(1)先复制其左子树;
(2)再复制其右子树;
(3)生成一个新结点,将根复制。
BiTreeGetTreeNode(TElemTypeitem,BiTreelptr,BiTreerptr)
{//生成一个其元素值为item,左指针为lpttr,右指针为rptr的结点
BiTreet;
t=(BiTree)malloc(sizeof(BiTNode));
t->
data=item;
lchild=lptr;
rchild=rptr;
BiTreeCopyTree(BiTreeT)
{//已知二叉树的根指针T,返回它的复制品的根指针
BiTreenewlptr,newrptr,newnode;
returnNULL;
//复制一颗空树
if(T->
newlptr=CopyTree(T->
//复制(遍历)其左子树
newlptr=NULL;
newrptr=CopyTree(T->
//复制(遍历)其右子树
newrptr=NULL;
newnode=GetTreeNode(T->
data,newlptr,newrptr);
//生成根结点
returnnewnode;
4、广义表形式打印二叉树
为了让打印的二叉树更形象,更清楚的反映二叉树各结点的关系,采用广义表形式打印则可以满足要求。
(1)打印根结点,若其还有孩子,则输出“(”;
(2)若有左孩子,则打印左子树;
(3)若还有右子树,则先打印“,”区分左右孩子,再打印右子树,并输出“)”表示输除完毕。
voidprint(BiTreeT)
{//广义表形式打印二叉树
%c"
T->
if(T->
=NULL||T->
=NULL)//该结点还有孩子
printf("
("
print(T->
//广义表打印左子树
printf("
"
//广义表打印右子树
)"
5、二叉树的常见运算
1)求二叉树的叶子数
(1)若该结点无孩子,则表示为叶子,计数器加一;
(2)若该结点右孩子,求其左子树的的叶子;
(3)再求其右子树的叶子。
intLeafNum(BiTreeT)
{//统计叶子数
intstaticn=0;
//定义一个静态局部变量作为计数器
lchild==NULL&
&
T->
rchild==NULL)//结点无孩子
n++;
//计数器加一
LeafNum(T->
//求左子树的叶子数
//求右子树的叶子数
returnn;
2)求不同的度的结点数
(1)定义一个静态局部数组变量来统计不同度的结点数
(2)若该结点既有左孩子又有右孩子则度为2的计数器加一,若该节点只有左孩子或只有右孩子,则度为1的结点数的计数器加一、
(3)在对其左右子树进行相同操作。
int*JudgeCBT(BiTreeT)
{//统计不同度的结点数
intstaticd[3]={0};
//d[1]作为度为1的计数器,d[2]作为度为2的计数器
=NULL&
=NULL)//左右孩子都有
d[2]++;
{//只有一个孩子
if(T->
rchild==NULL)
d[1]++;
else
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 二叉 基本 操作 运算 报告