广工数据结构实验报告平衡二叉树Word文档下载推荐.docx
- 文档编号:4187212
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:28
- 大小:165.62KB
广工数据结构实验报告平衡二叉树Word文档下载推荐.docx
《广工数据结构实验报告平衡二叉树Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《广工数据结构实验报告平衡二叉树Word文档下载推荐.docx(28页珍藏版)》请在冰点文库上搜索。
二叉树
1.2
5
堆
6
二叉排序树
7
平衡二叉树
1.3
8
树
9
并查集
10
B树
1.4
11
有向图
12
无向图
13
有向带权图
注:
如果基本操作数量较多,可选择实现其中一个基本操作子集。
实验要求
实验要求如下:
1.首先了解设计的任务,然后根据自己的基础和能力从中选择一题。
一般来说,选择题目应以在规定的时间内能完成,并能得到应有的锻炼为原则。
若学生对教材以外的相关题目较感兴趣,希望选作实验的题目时,应征得指导教师的认可,并写出明确的抽象数据类型定义及说明。
2.实验前要作好充分准备,包括:
理解实验要求,掌握辅助工具的使用,了解该抽象数据类型的定义及意义,以及其基本操作的算法并设计合理的存储结构。
3.实验时严肃认真,要严格按照要求独立进行设计,不能随意更改。
注意观察并记录各种错误现象,纠正错误,使程序满足预定的要求,实验记录应作为实验报告的一部分。
4.实验后要及时总结,写出实验报告,并附所打印的问题解答、程序清单,所输入的数据及相应的运行结果。
编程环境
本次实验设计采用C++语言,在MicrosoftVisualStudio2010IDE下完成。
所创建的项目类型Win32控制台应用程序:
抽象数据类型及接口简要描述
本次数据结构实验设计我选择的是二叉平衡树(AVL),使用C++面向对象编程语言实现。
利用C++泛型编程技术完成AVL类AVLTree。
抽象数据类型
1.平衡二叉树结点的ADT为:
template<
typenameT>
classAVLTreeNode
{
public:
T_key;
//结点关键字
int_bf;
//结点平衡因子
AVLTreeNode*_lchild;
//结点的左孩指针
AVLTreeNode*_rchild;
//结点的右孩指针
//构造函数
AVLTreeNode(Tkey,AVLTreeNode*lchild,AVLTreeNode*rchild,boolbf)
:
_key(key),_lchild(lchild),_rchild(rchild),_bf(bf){};
};
2.平衡二叉树类AVLTree的定义为:
classAVLTree
private:
AVLTreeNode<
T>
*_Root;
//树的根结点.
bool_taller;
//树是否长高的标记
AVLTree(){_Root=NULL;
//默认构造函数
~AVLTree(){};
//析构函数
//遍历操作
voidpreOrder();
//前序
voidinOrder();
//中序
voidpostOrder();
//后序
boolinsert(Tkey);
//插入
voidprint();
//打印
*search(Tkey);
//二叉树的查找
*minimumNode();
//查找最小的结点
*maxmumNode();
//查找最大的结点
voidremove(Tkey);
//删除结点
voiddestory();
//销毁AVL树
//删除时的左平衡操作
voiddelLeftBalance(AVLTreeNode<
*&
tree,intchildBf);
//删除时的右平衡操作
voiddelRightBalance(AVLTreeNode<
tree,intchildBf);
//中序遍历
voidinOrder(AVLTreeNode<
tree);
//前序遍历
voidpreOrder(AVLTreeNode<
//后序遍历
voidpostOrder(AVLTreeNode<
//像二叉树中插入新结点
boolinsert(AVLTreeNode<
tree,Tkey,bool&
taller);
//插入时导致LL型失衡的右旋操作
voidrightRotate(AVLTreeNode<
*&
//插入时导致RR型失衡的左旋左旋
voidleftRotate(AVLTreeNode<
//左平衡处理
voidleftBalance(AVLTreeNode<
//右平衡处理
voidrightBalance(AVLTreeNode<
//删除时的左平衡处理
voiddLeftBalance(AVLTreeNode<
tree);
//删除时的右平衡处理
voiddRightBalance(AVLTreeNode<
//打印二叉树
voidprint(AVLTreeNode<
//查找二叉树中指定结点
*search(AVLTreeNode<
*&
tree,Tkey);
//查找二叉树最小的结点
*minimumNode(AVLTreeNode<
//查找二叉树最大的结点
*maxmumNode(AVLTreeNode<
//删除指定关键字的结点
AVLTreeNode<
*remove(AVLTreeNode<
tree,AVLTreeNode<
*z);
//销毁二叉树,释放所有申请的空间
voiddestory(AVLTreeNode<
接口简要描述
3.遍历操作接口
遍历二叉树是指从根结点出发,按照某种次序访问二叉树所有结点,使得每个结点被且仅被访问一次,这里的访问可以是输出、比较、更新、查看结点信息等各种操作。
遍历是二叉树的一类重要操作,也是二叉树的其他一些操作和各种应用算法的基本框架。
用V表示根节点,用L表示左孩子,用R表示右孩子,且规定先L后R的访问顺序,则有VLR(前序)、LVR(中序)、LRV(后续)三种遍历算法。
对于图a中的二叉树,其遍历结果为:
前序遍历:
884719555098
中序遍历:
194750558898
后序遍历:
195055479888
AVLTree类提供了三个遍历接口,分别是前序、中序、后续遍历。
这三个接口都使用递归算法实现,调用遍历接口可以得到相应遍历次序的序列。
4.插入接口
插入操作是AVL树的关键操作,用于向AVL插入新的结点,其难点在于每次插入操作都要维护树的平衡性。
向平衡二叉树中插入一个新结点后如果破坏了平衡二叉树的平衡性,首先要找出插入新结点后失去平衡的最小子树(最小失衡子树)根结点的指针,然后再调整这个子树中有关结点之间的连接关系,使之成为新的平衡二叉树。
当进行插入操作时,找到该需要插入结点的位置插入后,从该结点起向上寻找,第一个不平衡的结点(平衡因子变成了-2或2)。
以该结点为根的子树即为最小失衡子树。
二叉排序树转成平衡二叉树失去平衡后进行调整的四种情况:
(1)单向右旋平衡处理。
当在左子树插入左结点,使平衡因子由1增至2时。
(2)单向左旋平衡处理。
当在右子树中插入有节点,使平衡因子由-1增至-2时。
(3)双向旋转(先左后右)平衡处理。
当在左子树上插入右结点,使平衡因子由1增至2时。
(4)双向旋转(先右后左)平衡处理。
当在右子树上插入左结点,使平衡因子由-1增至-2时。
插入接口对上述的情况做了处理。
5.删除接口
删除操作与插入操作一样,需要在每次删除时维护树的平衡性,而且删除比插入需要处理的情况更加复杂。
在实验过程中我主要想法是抓住“判断树的高度是否降低,若是则进行平衡因子判断及结点调整”。
总的来说,导致树高度降低的原因就是某个结点的平衡因子由1(或-1)变成0的时候。
删除操作采用递归算法实现。
6.二叉树查找接口
AVLTree类供提供了三种查找操作,一种是传统意义上的查找某个指定关键字的结点,另外两个是查找关键字最小及最大结点。
查找算法使用递归实现。
7.打印二叉树接口
二叉树打印即描述二叉树的结构构成情况,例如描述某个结点的左孩子及右孩子指针指向,依据该接口的输出语句可描画出二叉树的结构。
打印接口同样采用递归算法来实现。
8.销毁二叉树接口
该接口将创建AVL树时申请的结点资源释放,使用递归算法将整棵二叉树进行销毁。
算法设计
1.孩子表示法存储结构
//定义并初始化一个新结点
//AVLTreeNode类的默认构造函数
2.//前序遍历
//接口
voidAVLTree<
:
preOrder()
preOrder(_Root);
}
//类的私有函数,供接口调用
preOrder(AVLTreeNode<
tree)
if(tree)
{
cout<
<
tree->
_key<
"
"
;
preOrder(tree->
_lchild);
_rchild);
}
3.//中序遍历
inOrder()
inOrder(_Root);
inOrder(AVLTreeNode<
inOrder(tree->
4.//后序遍历
postOrder()
postOrder(_Root);
postOrder(AVLTreeNode<
postOrder(tree->
5.//查找指定结点
*AVLTree<
search(AVLTreeNode<
tree,Tkey)
*temp=tree;
while(temp!
=NULL)
if(temp->
_key==key)
returntemp;
elseif(temp->
_key>
key)
temp=temp->
_lchild;
else
_rchild;
returnNULL;
6.//查找最小结点
minimumNode()
returnminimumNode(_Root);
minimumNode(AVLTreeNode<
while(temp->
_lchild)
temp=temp->
returntemp;
7.//查找最大结点
maxmumNode()
returnmaxmumNode(_Root);
maxmumNode(AVLTreeNode<
*temp=tree;
_rchild)
8.//打印二叉树
print()
print(_Root);
print(AVLTreeNode<
if(tree)//如果tree不为空
if(tree->
_lchild)//结点有左孩子
cout<
节点"
有左孩子为"
_lchild->
endl;
有右孩子为"
_rchild->
print(tree->
}
9.//销毁二叉树
destory()
destory(_Root);
destory(AVLTreeNode<
if(tree->
_lchild!
=NULL)
destory(tree->
_rchild!
_lchild==NULL&
&
_rchild==NULL)
delete(tree);
tree=NULL;
10.//插入函数
boolAVLTree<
insert(Tkey)
_taller=false;
returninsert(_Root,key,_taller);
insert(AVLTreeNode<
tree,Te,bool&
taller)
if(!
tree)
tree=newAVLTreeNode<
(e,NULL,NULL,0);
tree->
_bf=EH;
_lchild=tree->
_rchild=NULL;
taller=true;
else
if(e==tree->
_key)//如果e已经存在
{
taller=false;
//则树不长高
returnfalse;
}
if(e<
_key)
if(!
insert(tree->
_lchild,e,taller))
returnfalse;
if(taller)
{
switch(tree->
_bf)
{
caseLH:
leftBalance(tree);
taller=false;
break;
caseRH:
rightBalance(tree);
caseEH:
tree->
_bf=LH;
taller=true;
break;
}
}
_rchild,e,taller))
tree->
taller=false;
caseEH:
_bf=RH;
taller=true;
returntrue;
11.//左旋函数
leftRotate(AVLTreeNode<
*R=tree->
tree->
_rchild=R->
R->
_lchild=tree;
tree=R;
12.//右旋函数
rightRotate(AVLTreeNode<
*L=tree->
_lchild=L->
L->
_rchild=tree;
tree=L;
13.//左平衡处理
leftBalance(AVLTreeNode<
*L;
*Lr;
L=tree->
//L指向tree的左孩子
switch(L->
_bf)//检查左孩子的平衡度,并做相应的处理
caseLH:
//新结点插入在左子树的左孩子上,需要做单右旋处理
tree->
_bf=L->
_bf=EH;
rightRotate(tree);
break;
caseRH:
//新结点插入在左子树的右孩子上,需要做先左后右旋转处理
Lr=L->
switch(Lr->
caseLH:
L->
_bf=RH;
_bf=LH;
_bf=L->
Lr->
leftRotate(tree->
14.//右平衡处理
rightBalance(AVLTreeNode<
*R;
*Rl;
R=tree->
switch(R->
caseRH:
//新结点插入到右子树的右结点上,单纯做左旋处理。
tree->
R->
leftRotate(tree);
break;
caseEH:
_bf=RH;
caseLH:
//新结点插入到右子树的左结点上,做先右后左处理。
Rl=R->
switch(Rl->
caseLH:
R->
caseEH:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 报告 平衡 二叉