广工数据结构实验报告平衡二叉树.docx
- 文档编号:2221377
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:28
- 大小:165.62KB
广工数据结构实验报告平衡二叉树.docx
《广工数据结构实验报告平衡二叉树.docx》由会员分享,可在线阅读,更多相关《广工数据结构实验报告平衡二叉树.docx(28页珍藏版)》请在冰点文库上搜索。
广工数据结构实验报告平衡二叉树
数据结构设计性实验报告
课程名称_____数据结构实验_
题目名称平衡二叉树
学生学院__计算机学院______
专业班级_
学号__________
学生姓名________
指导教师__________
2015年6月14日
目录
一、设计任务、要求以及所用环境及工具4
实验设计任务4
实验要求4
编程环境4
抽象数据类型及接口简要描述5
抽象数据类型5
接口简要描述7
算法设计8
程序测试17
测试代码17
测试结果18
测试分析20
思考与小结21
一、
设计任务、要求以及所用环境及工具
实验设计任务
以教材中讨论的各种抽象数据类型为对象,利用C语言的数据类型表示和实现其中某个抽象数据类型。
可选的抽象数据类型如下表所列:
编号
抽象数据类型
基本难度
存储结构
1
栈和队列
1.0
顺序和链接
2
线性表
1.0
顺序和链接
3
哈希表
1.1
任选
4
二叉树
1.2
任选
5
堆
1.2
任选
6
二叉排序树
1.2
任选
7
平衡二叉树
1.3
任选
8
树
1.2
任选
9
并查集
1.2
任选
10
B树
1.4
任选
11
有向图
1.3
任选
12
无向图
1.3
任选
13
有向带权图
1.3
任选
注:
如果基本操作数量较多,可选择实现其中一个基本操作子集。
实验要求
实验要求如下:
1.首先了解设计的任务,然后根据自己的基础和能力从中选择一题。
一般来说,选择题目应以在规定的时间内能完成,并能得到应有的锻炼为原则。
若学生对教材以外的相关题目较感兴趣,希望选作实验的题目时,应征得指导教师的认可,并写出明确的抽象数据类型定义及说明。
2.实验前要作好充分准备,包括:
理解实验要求,掌握辅助工具的使用,了解该抽象数据类型的定义及意义,以及其基本操作的算法并设计合理的存储结构。
3.实验时严肃认真,要严格按照要求独立进行设计,不能随意更改。
注意观察并记录各种错误现象,纠正错误,使程序满足预定的要求,实验记录应作为实验报告的一部分。
4.实验后要及时总结,写出实验报告,并附所打印的问题解答、程序清单,所输入的数据及相应的运行结果。
编程环境
本次实验设计采用C++语言,在MicrosoftVisualStudio2010IDE下完成。
所创建的项目类型Win32控制台应用程序:
抽象数据类型及接口简要描述
本次数据结构实验设计我选择的是二叉平衡树(AVL),使用C++面向对象编程语言实现。
利用C++泛型编程技术完成AVL类AVLTree。
抽象数据类型
1.平衡二叉树结点的ADT为:
template
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的定义为:
template
classAVLTree
{
private:
AVLTreeNode
bool_taller;//树是否长高的标记
public:
AVLTree(){_Root=NULL;};//默认构造函数
~AVLTree(){};//析构函数
//遍历操作
voidpreOrder();//前序
voidinOrder();//中序
voidpostOrder();//后序
boolinsert(Tkey);//插入
voidprint();//打印
AVLTreeNode
AVLTreeNode
AVLTreeNode
voidremove(Tkey);//删除结点
voiddestory();//销毁AVL树
private:
//删除时的左平衡操作
voiddelLeftBalance(AVLTreeNode
//删除时的右平衡操作
voiddelRightBalance(AVLTreeNode
//中序遍历
voidinOrder(AVLTreeNode
//前序遍历
voidpreOrder(AVLTreeNode
//后序遍历
voidpostOrder(AVLTreeNode
//像二叉树中插入新结点
boolinsert(AVLTreeNode
//插入时导致LL型失衡的右旋操作
voidrightRotate(AVLTreeNode
//插入时导致RR型失衡的左旋左旋
voidleftRotate(AVLTreeNode
//左平衡处理
voidleftBalance(AVLTreeNode
//右平衡处理
voidrightBalance(AVLTreeNode
//删除时的左平衡处理
voiddLeftBalance(AVLTreeNode
//删除时的右平衡处理
voiddRightBalance(AVLTreeNode
//打印二叉树
voidprint(AVLTreeNode
//查找二叉树中指定结点
AVLTreeNode
//查找二叉树最小的结点
AVLTreeNode
//查找二叉树最大的结点
AVLTreeNode
//删除指定关键字的结点
AVLTreeNode
//销毁二叉树,释放所有申请的空间
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类的默认构造函数
AVLTreeNode(Tkey,AVLTreeNode*lchild,AVLTreeNode*rchild,boolbf)
:
_key(key),_lchild(lchild),_rchild(rchild),_bf(bf){};
2.//前序遍历
//接口
template
voidAVLTree
:
preOrder()
{
preOrder(_Root);
}
//类的私有函数,供接口调用
template
voidAVLTree
:
preOrder(AVLTreeNode
{
if(tree)
{
cout<
preOrder(tree->_lchild);
preOrder(tree->_rchild);
}
}
3.//中序遍历
template
voidAVLTree
:
inOrder()
{
inOrder(_Root);
}
template
voidAVLTree
:
inOrder(AVLTreeNode
{
if(tree)
{
inOrder(tree->_lchild);
cout<
inOrder(tree->_rchild);
}
}
4.//后序遍历
//后序遍历
template
voidAVLTree
:
postOrder()
{
postOrder(_Root);
}
template
voidAVLTree
:
postOrder(AVLTreeNode
{
if(tree)
{
postOrder(tree->_lchild);
postOrder(tree->_rchild);
cout<
}
}
5.//查找指定结点
template
AVLTreeNode
:
search(AVLTreeNode
{
AVLTreeNode
while(temp!
=NULL)
{
if(temp->_key==key)
returntemp;
elseif(temp->_key>key)
temp=temp->_lchild;
else
temp=temp->_rchild;
}
returnNULL;
}
6.//查找最小结点
template
AVLTreeNode
:
minimumNode()
{
returnminimumNode(_Root);
}
template
AVLTreeNode
:
minimumNode(AVLTreeNode
{
AVLTreeNode
while(temp->_lchild)
{
temp=temp->_lchild;
}
returntemp;
}
7.//查找最大结点
template
AVLTreeNode
:
maxmumNode()
{
returnmaxmumNode(_Root);
}
template
AVLTreeNode
:
maxmumNode(AVLTreeNode
{
AVLTreeNode
while(temp->_rchild)
{
temp=temp->_rchild;
}
returntemp;
}
8.//打印二叉树
template
voidAVLTree
:
print()
{
print(_Root);
}
template
voidAVLTree
:
print(AVLTreeNode
{
if(tree)//如果tree不为空
{
if(tree->_lchild)//结点有左孩子
cout<<"节点"< if(tree->_rchild) cout<<"节点"< print(tree->_lchild); print(tree->_rchild); } } 9.//销毁二叉树 template voidAVLTree : destory() { destory(_Root); } template voidAVLTree : destory(AVLTreeNode { if(tree->_lchild! =NULL) destory(tree->_lchild); if(tree->_rchild! =NULL) destory(tree->_rchild); if(tree->_lchild==NULL&&tree->_rchild==NULL) { delete(tree); tree=NULL; } } 10.//插入函数 template boolAVLTree : insert(Tkey) { _taller=false; returninsert(_Root,key,_taller); } template boolAVLTree : insert(AVLTreeNode { if(! tree) { tree=newAVLTreeNode tree->_bf=EH; tree->_lchild=tree->_rchild=NULL; taller=true; } else { if(e==tree->_key)//如果e已经存在 { taller=false;//则树不长高 returnfalse; } if(e { if(! insert(tree->_lchild,e,taller)) returnfalse; if(taller) { switch(tree->_bf) { caseLH: leftBalance(tree); taller=false; break; caseRH: rightBalance(tree); taller=false; break; caseEH: tree->_bf=LH; taller=true; break; } } } else { if(! insert(tree->_rchild,e,taller)) returnfalse; if(taller) { switch(tree->_bf) { caseLH: tree->_bf=EH; taller=false; break; caseRH: rightBalance(tree); taller=false; break; caseEH: tree->_bf=RH; taller=true; break; } } } } returntrue; } 11.//左旋函数 template voidAVLTree : leftRotate(AVLTreeNode { AVLTreeNode tree->_rchild=R->_lchild; R->_lchild=tree; tree=R; } 12.//右旋函数 template voidAVLTree : rightRotate(AVLTreeNode { AVLTreeNode tree->_lchild=L->_rchild; L->_rchild=tree; tree=L; } 13.//左平衡处理 template voidAVLTree : leftBalance(AVLTreeNode { AVLTreeNode AVLTreeNode L=tree->_lchild;//L指向tree的左孩子 switch(L->_bf)//检查左孩子的平衡度,并做相应的处理 { caseLH: //新结点插入在左子树的左孩子上,需要做单右旋处理 tree->_bf=L->_bf=EH; rightRotate(tree); break; caseRH: //新结点插入在左子树的右孩子上,需要做先左后右旋转处理 Lr=L->_rchild; switch(Lr->_bf) { caseLH: L->_bf=EH; tree->_bf=RH; break; caseRH: tree->_bf=EH; L->_bf=LH; break; caseEH: tree->_bf=L->_bf=EH; break; } Lr->_bf=EH; leftRotate(tree->_lchild); rightRotate(tree); } } 14.//右平衡处理 template voidAVLTree : rightBalance(AVLTreeNode { AVLTreeNode AVLTreeNode R=tree->_rchild; switch(R->_bf) { caseRH: //新结点插入到右子树的右结点上,单纯做左旋处理。 tree->_bf=EH; R->_bf=EH; leftRotate(tree); break; caseEH: tree->_bf=RH; R->_bf=LH; leftRotate(tree); break; caseLH: //新结点插入到右子树的左结点上,做先右后左处理。 Rl=R->_lchild; switch(Rl->_bf) { caseLH: tree->_bf=EH; R->_bf=LH; break; caseEH:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 报告 平衡 二叉
![提示](https://static.bingdoc.com/images/bang_tan.gif)