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

《2015广工数据结构实验报告平衡二叉树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构设计性实验报告课程名称_____数据结构实验_题目名称平衡二叉树学生学院__计算机学院______专业班级_学号__________学生姓名________指导教师__________2015年6月14日目录一、设计任务、要求以及所用环境及工具4实验设计任务4实验要求4编程环境4抽象数据类型及接口简要描述5抽象数据类型5接口简要描述7算法设计8程序测试17测试代码17测试结果18测试分析20思考与小结21设计任务、要求以及所用环境及工具实验设计任务以教材中讨论的各种抽象数据类型为对象，利用C语言的数据类型表示和实现其中某个抽象数据类型。可选的抽

2、象数据类型如下表所列：编号抽象数据类型基本难度存储结构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．首先了解设计的任务，然后根据自己的基础和能力从中选择一题。一般来说，选择题目应以在规定的时间内能完成，并能得到应有的锻炼为原则。若学生对教材以外的相关题目较感兴趣

3、，希望选作实验的题目时，应征得指导教师的认可，并写出明确的抽象数据类型定义及说明。2.实验前要作好充分准备，包括：理解实验要求，掌握辅助工具的使用，了解该抽象数据类型的定义及意义，以及其基本操作的算法并设计合理的存储结构。3.实验时严肃认真，要严格按照要求独立进行设计，不能随意更改。注意观察并记录各种错误现象，纠正错误，使程序满足预定的要求，实验记录应作为实验报告的一部分。4.实验后要及时总结，写出实验报告，并附所打印的问题解答、程序清单，所输入的数据及相应的运行结果。编程环境本次实验设计采用C++语言，在MicrosoftVisualStudio20

4、10IDE下完成。所创建的项目类型Win32控制台应用程序：抽象数据类型及接口简要描述本次数据结构实验设计我选择的是二叉平衡树（AVL），使用C++面向对象编程语言实现。利用C++泛型编程技术完成AVL类AVLTree。抽象数据类型1.平衡二叉树结点的ADT为：templateclassAVLTreeNode{public:T_key;//结点关键字int_bf;//结点平衡因子AVLTreeNode*_lchild;//结点的左孩指针AVLTreeNode*_rchild;//结点的右孩指针//构造函数AVLTreeNode(T

5、key,AVLTreeNode*lchild,AVLTreeNode*rchild,boolbf):_key(key),_lchild(lchild),_rchild(rchild),_bf(bf){};};1.平衡二叉树类AVLTree的定义为：templateclassAVLTree{private:AVLTreeNode*_Root;//树的根结点.bool_taller;//树是否长高的标记public:AVLTree(){_Root=NULL;};//默认构造函数~AVLTree(){};//析构函数//遍历操作v

6、oidpreOrder();//前序voidinOrder();//中序voidpostOrder();//后序boolinsert(Tkey);//插入voidprint();//打印AVLTreeNode*search(Tkey);//二叉树的查找AVLTreeNode*minimumNode();//查找最小的结点AVLTreeNode*maxmumNode();//查找最大的结点voidremove(Tkey);//删除结点voiddestory();//销毁AVL树private://删除时的左平衡操作voiddelLeft

7、Balance(AVLTreeNode*&tree,intchildBf);//删除时的右平衡操作voiddelRightBalance(AVLTreeNode*&tree,intchildBf);//中序遍历voidinOrder(AVLTreeNode*&tree);//前序遍历voidpreOrder(AVLTreeNode*&tree);//后序遍历voidpostOrder(AVLTreeNode*&tree);//像二叉树中插入新结点boolinsert(AVLTreeNode*&tree,Tkey,bo

8、ol&taller);//插入时导致LL型失衡的右旋操作voidrightRotate(AVL