《2021新版广工数据结构实验报告平衡二叉树.docx》由会员分享，可在线阅读，更多相关《2021新版广工数据结构实验报告平衡二叉树.docx（12页珍藏版）》请在三一文库上搜索。
1、2021新版广工数据结构实验报告平衡二叉树2020年新版广工数据结构实验报告平衡二叉树 数据结构设计性实验报告课程名称数据结构实验题目名称平衡二叉树学生学院_ 计算机学院专业班级_学 号学生姓名指导教师xxxx年6月14日目录 TOC o 1-5 h z o Current Document 一、 设计任务、要求以及所用环境及工具 return returntrue/ 左旋函数template typename Tvoid AVLTreeT:leftRotate(AVLTreeNodeT * tree) AVLTreeNodeT * R = tree-_rchild; tree-_rchild
2、= R-_lchild;R-_lchild = tree; tree = R;/ 右旋函数template typename Tvoid AVLTreeT:rightRotate(AVLTreeNodeT * tree) AVLTreeNodeT * L = tree-_lchild; tree-_lchild = L-_rchild;L-_rchild= tree;tree = L;/ 左平衡处理template typename Tvoid AVLTreeT:leftBalance(AVLTreeNodeT * tree) AVLTreeNodeT * Lr; L =AVLTreeNode
3、T * Lr; L = tree-_lchild; switch (L-_bf) case LH :/L 指向 tree 的左孩子/ 检查左孩子的平衡度，并做相应的处理/ 新结点插入在左子树的左孩子上，需要做单右旋处理tree-_bf = L-_bf = EH; rightRotate(tree); break ;case RH: / 新结点插入在左子树的右孩子上，需要做先左后右旋转处理Lr = L-_rchild; switch (Lr-_bf) case LH :L-_bf = EH; tree-_bf= RH; break ;case RH: tree-_bf= EH; L-_bf =
4、LH; break ;case EH:tree-_bf=L-_bf = EH; break ; Lr-_bf = EH; leftRotate(tree-_lchild); rightRotate(tree);/ 右平衡处理 template typename T void AVLTreeT:rightBalance(AVLTreeNodeT * tree) AVLTreeNodeT *R; AVLTreeNodeT *Rl;R = tree-_rchild; switch (R-_bf)case RH: / 新结点插入到右子树的右结点上，单纯做左旋处理。tree -_bf = EH;R-_b
5、f = EH; leftRotate(tree); break ;case EH:tree-_bf = RH; R-_bf = LH; leftRotate(tree); break ;case LH: / 新结点插入到右子树的左结点上，做先右后左处理。Rl=R-_lchild;switch (Rl-_bf)case LH: tree-_bf= EH; R-_bf = LH; break ;case EH: tree-_bf=R-_bf = EH; break ;case RH: tree-_bf=EH; R-_bf = RH;break ;Rl-_bf = EH; rightRotate(t
6、ree-_rchild); leftRotate(tree);/ 删除结点时左平衡操作 template typename T void AVLTreeT:delLeftBalance(AVLTreeNodeT* tree , int childBf) if (tree-_lchild= NULL | childBf != EHtree-_lchild-_bf = EH)switch (tree-_bf)case LH: tree-_bf = EH; break ;case RH: rightBalance(tree); break ;case EH: tree-_bf = RH; break
7、 ;/ 删除结点时的右平衡操作 template typename T void AVLTreeT:delRightBalance(AVLTreeNodeT*tree , int childBf) if (tree-_rchild = NULL | childBf!= EHtree-_rchild-_bf = EH)switch (tree-_bf) case LH:leftBalance(tree); break ;case RH : tree-_bf =EH; break ;case EH:tree-_bf =LH; break ;程序测试测试代码/ AVLTree.cpp :定义控制台应
8、用程序的入口点。/#include stdafx.h#include iostream#include time.h#include AVLTree.h#define MAX 200using namespace std;int main()srand( ( unsigned )time( NULL ) );AVLTreeint atree;for (int i = 0;i10;i+)atree.ert(rand()%MAX);coutatree.print();coutatree.inOrder();coutendl;m*打印 AVL树*endl；中序遍历 AVL树*”endl;请输入查找的
9、数： * endl；int a ;while (cina)if (atree.search(a)cout 查找成功 endl;else cout 查找失败 endl; cin.clear();endl;cout * 请输入要删除的树节点关键字 *endl;while (cina) atree.remove(a);endl;cout 删除后的结果为： atree.inOrder(); coutendl;endl;atree.print();coutendl;cout 销毁二 AVL树endl;atree.destory();cout 销毁结果为： endl;atree.print();syste
10、m( pause );测试结果ITS 192*，畫输人要删醸拥对节点关漣字 強后的结臬为：4 IBB 12fr 138 143 155 173 175 182|匚卩RU二 |P |匠1 fi 3 3 s- 5 2 0 7 4 4 7 5 9 5 113 1-11- CJ LJ Llr Jr .J- iJ iJ 1却丿斗I#斗丿耳.1-.斗/ 3T-于干干干干-于 14孩孩孩；孩孩 2右右左右右右 12_J lr 3 -J -J 6 6 3 3 J 5 8 2 2 0 7 7 4-7 JI 1- JI Jx tI JI Jx 丄占告吿尸点占4点占”Au眞.s 二纹任Z “冃:冃巧6打有右孩壬加刘
11、巧邑打有右孩壬为1骂 讀;175着若雀丈为1翌gI MMWMJIM.M.M 34 1QB 12b 139 143 155 173 175 182.H.” U *Jl K, HltK KJt WJLK JI.K K j?点仙皇电樓壬划1芮 点萌晡芒营辛为銅 占蚀箱右遨壬为做 占诵有庁袴士光K3 点切錯右孩壬为肯5 点如有右孩子为15去测试分析程序代码使用rand（）随机函数随机产生值 0200之间测试结点数据，一共是10个结点。在上述测试中产生的10个节点值为：27 34 100 126 138 143 155 173 175 182结点的输入过程也是二叉平衡树的建立过程，打印查找描述岀插入操作
12、完成后形成的二叉 树，依据打印描述可以得到一下二叉树结构：（138 甜丿173(27 126143 ) I； 175 、 6100 j(155 ) ( 182 中序遍历该树可以按从大到小的顺序输出结点：27 34 100 126 138 143 155 173 175 182查找平衡二叉树中的结点27与34都查找成功。删除结点：删除结点27时，结点34的平衡因子由-1变成-2，故需要对结点34做平衡处理， 处理方法是使用34的直接前驱（没有）或直接后继（100）来代替34,删掉34的 直接后继100。删除操作完成后平衡二叉树如下图所示：138 |I100( 173 )34 I 126 ； 14
13、3 )175155182同理的，删除结点138时，使用138的直接前驱（126）来代替138，同时从树中删除138的直 接前驱。删除结果如下图所示：126100 )( 173 )34143! 175 )155 ) I 182最后是销毁二叉树并打印岀销毁后的二叉树，可以看到销毁后二叉树已经没有内容可供打 印了。思考与小结平衡二叉树的难点就在于插入与删除时维护树的平衡度上，在插入上认清楚LL、RRLR RL四种旋转情况是关键，而在删除时要时刻抓住哪种结点的删除会导致树高度的减低 来进行分析。AVL的删除很多书基本没有提及，复杂的情况只能自己在纸上慢慢地画出来分 析出来，这个过程中也学到了很多东西。
14、采用C+来完成这次的实验，是想利用C+面向对象提供的技术来完成 AVL这种数据结构的封装。刚开始写AVLTree这个类时，对成员函数如何递归感到有点困惑，一方面，如果将类的成员数据暴露给类用户，则会破坏类的封装性，而如果成员函数参数不含数据成员又 无法完成递归。思考之后，才想到一个解决的办法：像类用户提供一个接口，该接口在类内 部实现上调用重载函数进行递归，这样就能解决上面问题。实际上书里所描述的平衡二叉树准确的说应该是AVL树，AVL树属于平衡二叉树的一种，写AVL树的空余时间，我也同时了解了其他的平衡二叉树如红黑树等等，它们都有各种适用的场合，如红黑树常作为数据库文件索引的数据结构。在我看来，学_数据结构应该要举一 反三，有相同作用、相似类型的数据结构应该在一起比较学_，这样能更好地掌握。在测试程序的时候出了 BUG通过断点、变量监视等调试后发现是左平衡函数中左旋转函数调用参数写错，算法设计经常会出现莫名其妙的错误，所要做的就是冷静调试了