2015广工数据结构实验报告平衡二叉树.doc

数据结构设计性实验报告 课程名称_数据结构实验 _ 题目名称 平衡二叉树 学生学院_ 计算机学院_ 专业班级_ 学 号_ _学生姓名_ _ _指导教师_ _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任选10B树1.4任选11有向图1.3任选12无向图1.3任选13有向带权图1.3任选注：如果基本操作数量较多，可选择实现其中一个基本操作子集。实验要求实验要求如下：1首先了解设计的任务，然后根据自己的基础和能力从中选择一题。一般来说，选择题目应以在规定的时间内能完成，并能得到应有的锻炼为原则。 若学生对教材以外的相关题目较感兴趣，希望选作实验的题目时，应征得指导教师的认可，并写出明确的抽象数据类型定义及说明。2. 实验前要作好充分准备，包括：理解实验要求，掌握辅助工具的使用，了解该抽象数据类型的定义及意义，以及其基本操作的算法并设计合理的存储结构。3. 实验时严肃认真，要严格按照要求独立进行设计，不能随意更改。注意观察并记录各种错误现象，纠正错误，使程序满足预定的要求，实验记录应作为实验报告的一部分。4. 实验后要及时总结，写出实验报告，并附所打印的问题解答、程序清单，所输入的数据及相应的运行结果。编程环境本次实验设计采用C+语言，在Microsoft Visual Studio2010 IDE下完成。所创建的项目类型Win32控制台应用程序：抽象数据类型及接口简要描述本次数据结构实验设计我选择的是二叉平衡树（AVL），使用C+面向对象编程语言实现。利用C+泛型编程技术完成AVL类AVLTree。抽象数据类型1. 平衡二叉树结点的ADT为：template class AVLTreeNodepublic:T _key; /结点关键字int _bf; /结点平衡因子AVLTreeNode *_lchild ; /结点的左孩指针AVLTreeNode *_rchild ; /结点的右孩指针/构造函数AVLTreeNode(T key ,AVLTreeNode *lchild , AVLTreeNode *rchild ,bool bf):_key(key), _lchild(lchild),_rchild(rchild),_bf(bf);2. 平衡二叉树类AVLTree的定义为：template class AVLTree private:AVLTreeNode * _Root ;/树的根结点.bool _taller ; /树是否长高的标记public:AVLTree()_Root=NULL; /默认构造函数AVLTree();/析构函数/遍历操作void preOrder(); /前序void inOrder(); /中序void postOrder(); /后序bool insert (T key);/插入void print();/打印AVLTreeNode* search (T key) ; /二叉树的查找AVLTreeNode* minimumNode();/查找最小的结点AVLTreeNode* maxmumNode();/查找最大的结点void remove(T key); /删除结点void destory ();/销毁AVL树private: /删除时的左平衡操作void delLeftBalance(AVLTreeNode*& tree , int childBf); /删除时的右平衡操作void delRightBalance(AVLTreeNode*&tree ,int childBf);/中序遍历void inOrder(AVLTreeNode*& tree); /前序遍历void preOrder(AVLTreeNode*& tree);/后序遍历void postOrder(AVLTreeNode*& tree); /像二叉树中插入新结点bool insert(AVLTreeNode*& tree ,T key,bool &taller); /插入时导致LL型失衡的右旋操作void rightRotate(AVLTreeNode *& tree); /插入时导致RR型失衡的左旋左旋void leftRotate(AVLTreeNode *& tree); /左平衡处理void leftBalance(AVLTreeNode *& tree); /右平衡处理void rightBalance(AVLTreeNode *& tree); /删除时的左平衡处理void dLeftBalance(AVLTreeNode *& tree); /删除时的右平衡处理void dRightBalance(AVLTreeNode *& tree); /打印二叉树void print(AVLTreeNode*& tree); /查找二叉树中指定结点AVLTreeNode* search(AVLTreeNode* &tree,T key) ;/查找二叉树最小的结点AVLTreeNode* minimumNode(AVLTreeNode*& tree);/查找二叉树最大的结点AVLTreeNode* maxmumNode(AVLTreeNode*& tree); /删除指定关键字的结点AVLTreeNode* remove(AVLTreeNode*&tree,AVLTreeNode*z); /销毁二叉树，释放所有申请的空间void destory(AVLTreeNode*& tree);接口简要描述3. 遍历操作接口遍历二叉树是指从根结点出发，按照某种次序访问二叉树所有结点，使得每个结点被且仅被访问一次，这里的访问可以是输出、比较、更新、查看结点信息等各种操作。遍历是二叉树的一类重要操作，也是二叉树的其他一些操作和各种应用算法的基本框架。用V表示根节点，用L表示左孩子，用R表示右孩子，且规定先L后R的访问顺序，则有VLR（前序）、LVR（中序）、LRV（后续）三种遍历算法。对于图a中的二叉树，其遍历结果为：前序遍历：88 47 19 55 50 98中序遍历：19 47 50 55 88 98 后序遍历：19 50 55 47 98 88AVLTree类提供了三个遍历接口，分别是前序、中序、后续遍历。这三个接口都使用递归算法实现，调用遍历接口可以得到相应遍历次序的序列。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(T key ,AVLTreeNode *lchild , AVLTreeNode *rchild ,bool bf):_key(key), _lchild(lchild),_rchild(rchild),_bf(bf);2. /前序遍历/接口 templatevoid AVLTree:preOrder()preOrder(_Root);/类的私有函数，供接口调用templatevoid AVLTree:preOrder(AVLTreeNode*& tree)if(tree)cout_key_lchild);preOrder(tree-_rchild);3. /中序遍历template void AVLTree:inOrder()inOrder(_Root);template void AVLTree:inOrder(AVLTreeNode*& tree)if(tree)inOrder(tree-_lchild);cout_key_rchild);4. /后序遍历 /后序遍历template void AVLTree:postOrder()postOrder(_Root);templatevoid AVLTree:postOrder(AVLTreeNode*& tree)if(tree)postOrder(tree-_lchild);postOrder(tree-_rchild);cout_key ;5. /查找指定结点 template AVLTreeNode* AVLTree:search(AVLTreeNode* &tree,T key) AVLTreeNode* temp = tree;while(temp != NULL)if(temp-_key = key)return temp;else if(temp-_keykey)temp = temp-_lchild;elsetemp = temp-_rchild;return NULL;6. /查找最小结点template AVLTreeNode* AVLTree:minimumNode()return minimumNode(_Root);templateAVLTreeNode* AVLTree:minimumNode(AVLTreeNode*& tree)AVLTreeNode* temp = tree;while(temp-_lchild)temp= temp-_lchild;return temp;7. /查找最大结点template AVLTreeNode* AVLTree:maxmumNode()return maxmumNode(_Root);template AVLTreeNode* AVLTree:maxmumNode(AVLTreeNode*& tree)AVLTreeNode* temp=tree;while(temp-_rchild)temp= temp-_rchild;return temp;8. /打印二叉树templatevoid AVLTree:print()print(_Root);templatevoid AVLTree:print(AVLTreeNode*& tree)if(tree) /如果tree不为空if(tree-_lchild) /结点有左孩子cout节点_key有左孩子为_lchild-_key_rchild)cout节点_key有右孩子为_rchild-_key_lchild);print(tree-_rchild); 9. /销毁二叉树templatevoid AVLTree:destory()destory(_Root);templatevoid AVLTree:destory(AVLTreeNode*& tree)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. /插入函数templatebool AVLTree:insert(T key)_taller= false;return insert(_Root ,key,_taller);templatebool AVLTree:insert(AVLTreeNode*& tree,T e ,bool &taller)if(!tree)tree = new AVLTreeNode(e ,NULL,NULL,0);tree-_bf= EH;tree-_lchild=tree-_rchild = NULL;taller = true;elseif(e=tree-_key) /如果e已经存在taller = false; /则树不长高return false;if(e_key)if(!insert(tree-_lchild,e,taller)return false;if(taller)switch(tree-_bf)case LH:leftBalance(tree);taller =false;break;case RH:rightBalance(tree);taller =false;break;case EH:tree-_bf=LH;taller=true;break;elseif(!insert(tree-_rchild,e,taller)return false;if(taller)switch(tree-_bf)case LH:tree-_bf= EH;taller = false;break;case RH:rightBalance(tree);taller = false;break;case EH:tree-_bf=RH;taller = true;break;return true;11. /左旋函数templatevoid AVLTree:leftRotate(AVLTreeNode *& tree)AVLTreeNode * R = tree-_rchild;tree-_rchild= R-_lchild;R-_lchild = tree;tree = R;12. /右旋函数templatevoid AVLTree:rightRotate(AVLTreeNode *& tree)AVLTreeNode * L = tree-_lchild;tree-_lchild = L-_rchild;L-_rchild= tree;tree = L;13. /左平衡处理templatevoid AVLTree:leftBalance(AVLTreeNode *& tree)AVLTreeNode * L;AVLTreeNode * Lr;L = tree-_lchild; /L指向tree的左孩子switch(L-_bf)/检查左孩子的平衡度，并做相应的处理case LH :/新结点插入在左子树的左孩子上，需要做单右旋处理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 = LH;break;case EH:tree-_bf=L-_bf = EH;break;Lr-_bf = EH;leftRotate(tree-_lchild);rightRotate(tree);14. /右平衡处理templatevoid AVLTree:rightBalance(AVLTreeNode *& tree)AVLTreeNode *R;AVLTreeNode *Rl;R = tree-_rchild;switch(R-_bf)case RH: /新结点插入到右子树的右结点上，单纯做左旋处理。tree -_bf = EH;R-_bf = 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(tree-_rchild);leftRotate(tree);15. /删除结点时左平衡操作templatevoid AVLTree:delLeftBalance(AVLTreeNode*& tree , int childBf)if(tree-_lchild= NULL | childBf != EH&tree-_lchild-_bf = EH)switch(tree-_bf)case LH:tree-_bf = EH;break;case RH:rightBalance(tree);break;case EH:tree-_bf = RH;break;16. /删除结点时的右平衡操作templatevoid AVLTree:delRightBalance(AVLTreeNode*&tree ,int childBf)if(tree-_rchild = NULL | childBf!= EH&tree-_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 : 定义控制台应用程序的入口点。/#include stdafx.h#include#include #include AVLTree.h#define MAX 200using namespace std;int main()srand( (unsigned)time( NULL ) );AVLTree atree;for(int i = 0;i10;i+)atree.insert(rand()%MAX);cout*打印AVL树*endl;atree.print();cout*中序遍历AVL树*endl;atree.inOrder();coutendl;cout*请输入查找的数：*a)if(atree.search(a)cout查找成功endl;elsecout查找失败endl;cin.clear();cout*请输入要删除的树节点关键字*a)atree.remove(a);cout删除后的结果为：endl;atree.inOrder();coutendl;atree.print();coutendl;cout销毁二AVL树endl;atree.destory();cout销毁结果为：endl;atree.print();system(pause);测试结果测试分析程序代码使用rand()随机函数随机产生值0200之间测试结点数据，一共是10个结点。在上述测试中产生的10个节点值为：27 34