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

数据结构设计性实验报告课程名称_____数据结构实验_题目名称平衡二叉树学生学院__计算机学院______专业班级_学号__________学生姓名________指导教师__________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++语言，在MicrosoftVisualStudio2010IDE下完成。所创建的项目类型Win32控制台应用程序：抽象数据类型及接口简要描述本次数据结构实验设计我选择的是二叉平衡树（AVL），使用C++面向对象编程语言实现。利用C++泛型编程技术完成AVL类AVLTree。抽象数据类型1.平衡二叉树结点的ADT为：templatetypenameTclassAVLTreeNode{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的定义为：templatetypenameTclassAVLTree{private:AVLTreeNodeT*_Root;//树的根结点.bool_taller;//树是否长高的标记public:AVLTree(){_Root=NULL;};//默认构造函数~AVLTree(){};//析构函数//遍历操作voidpreOrder();//前序voidinOrder();//中序voidpostOrder();//后序boolinsert(Tkey);//插入voidprint();//打印AVLTreeNodeT*search(Tkey);//二叉树的查找AVLTreeNodeT*minimumNode();//查找最小的结点AVLTreeNodeT*maxmumNode();//查找最大的结点voidremove(Tkey);//删除结点voiddestory();//销毁AVL树private://删除时的左平衡操作voiddelLeftBalance(AVLTreeNodeT*&tree,intchildBf);//删除时的右平衡操作voiddelRightBalance(AVLTreeNodeT*&tree,intchildBf);//中序遍历voidinOrder(AVLTreeNodeT*&tree);//前序遍历voidpreOrder(AVLTreeNodeT*&tree);//后序遍历voidpostOrder(AVLTreeNodeT*&tree);//像二叉树中插入新结点boolinsert(AVLTreeNodeT*&tree,Tkey,bool&taller);//插入时导致LL型失衡的右旋操作voidrightRotate(AVLTreeNodeT*&tree);//插入时导致RR型失衡的左旋左旋voidleftRotate(AVLTreeNodeT*&tree);//左平衡处理voidleftBalance(AVLTreeNodeT*&tree);//右平衡处理voidrightBalance(AVLTreeNodeT*&tree);//删除时的左平衡处理voiddLeftBalance(AVLTreeNodeT*&tree);//删除时的右平衡处理voiddRightBalance(AVLTreeNodeT*&tree);//打印二叉树voidprint(AVLTreeNodeT*&tree);//查找二叉树中指定结点AVLTreeNodeT*search(AVLTreeNodeT*&tree,Tkey);//查找二叉树最小的结点AVLTreeNodeT*minimumNode(AVLTreeNodeT*&tree);//查找二叉树最大的结点AVLTreeNodeT*maxmumNode(AVLTreeNodeT*&tree);//删除指定关键字的结点AVLTreeNodeT*remove(AVLTreeNodeT*&tree,AVLTreeNodeT*z);//销毁二叉树，释放所有申请的空间voiddestory(AVLTreeNodeT*&tree);};接口简要描述3.遍历操作接口遍历二叉树是指从根结点出发，按照某种次序访问二叉树所有结点，使得每个结点被且仅被访问一次，这里的访问可以是输出、比较、更新、查看结点信息等各种操作。遍历是二叉树的一类重要操作，也是二叉树的其他一些操作和各种应用算法的基本框架。用V表示根节点，用L表示左孩子，用R表示右孩子，且规定先L后R的访问顺序，则有VLR（前序）、LVR（中序）、LRV（后续）三种遍历算法。对于图a中的二叉树，其遍历结果为：前序遍历：884719555098中序遍历：194750558898后序遍历：195055479888AVLTree类提供了三个遍历接口，分别是前序、中序、后续遍历。这三个接口都使用递归算法实现，调用遍历接口可以得到相应遍历次序的序列。4.插入接口插入操作是AVL树的关键操作，用于向AVL插入新的结点，其难点在于每次插入操作都要维护树的平衡性。向平衡二叉树中插入一个新结点后如果破坏了平衡二叉树的平衡性，首先要找出插入新结点后失去平衡的最小子树（最小失衡子树）根结点的指针，然后再调整这个子树中有关结点之间的连接关系，使之成为新的平衡二叉树。当进行插入操作时，找到该需要插入结点的位置插入后，从该结点起向上寻找，第一个不平衡的结点（平衡因子变成了-2或2）。以该结点为根的子树即为最小失衡子树。二叉排序树转成平衡二叉树失去平衡后进行调整的四种情况：（1）单向右旋平衡处理。当在左子树插入左结点，使平衡因子由1增至2时。(2)单向左旋平衡处理。当在右子树中插入有节点，使平衡因子由-1增至-2时。（3）双向旋转（先左后右）平衡处理。当在左子树上插入右结点，使平衡因子由1增至2时。(4)双向旋转（先右后左）平衡处理。当在右子树上插入左结点，使平衡因子由-1增至-2时。插入接口对上述的情况做了处理。5.删除接口删除操作与插入操作一样，需