文档介绍：数据结构与算法分析实验报告沈阳工程学院学生实验报告实验题目: 班级网络本112学号27姓名郑乐乐地点F606指导教师吕海华祝世东实验日期:XX年11月13日 1 2 3 4 华南农业大学信息学院综合性、设计性实验起止日期:XX秋教师签名:杨秋妹实验报告题目:实现平衡二叉排序树的各种算法班级:10软件工程7班姓名:黄定康学号:XX完成日期:XX/12/07 分析题目要求函数说明 voidR_rotate(ptr&t)-右旋转函数,从T开始做右旋转intcoutdeep(ptrt)-计算深度函数 voidL_rotate(ptr&t)-左旋转函数 voidleftbalance(ptr&t)-左平衡函数,从T开始做左平衡处理voidrightbalance(ptr&t)-右平衡函数 intinsertAVL(ptr&t,inte,int&taller)-插入结点函数voidpreorder(ptrt)-先序遍历 voidpreorder_2(ptrt)-先序遍历voidinorder(ptrt)-中序遍历voidinorder_2(ptrt)-中序遍历voidposorder(ptrt)-后序遍历 voidposorder_2(ptrt)-后序遍历 voiddfs(ptrt,inttype)-深度优先遍历voiddfs_2(ptrt,inttype)-(递归)深度优先遍历intbfs(ptrt)-层次便利 intdelete_node(ptr&t,int&shorter,inttemp);-删除结点函数intDelete(ptr&t,intshorter)-删除结点函数 inttransfer(ptr&t)-左右子树交换函数intcountleaf(ptrt)-计算叶节点 intcheckup(ptrt,inttemp)-从树t中查找temp是否存在,存在返回1否则返回0intmain()-主函数 voidshow_menu(ptrt)-简单的菜单函数输入形式及输入值范围输入形式:当树没创建时,先在第一行输入树的节点数目n,第二行再输入n个大于0的不重复整数,以空格隔开。删除结点时,直接输入要删除结点的值。输入范围:所有int类型的大于零的值,注意不能重复输入。输出形式输出形式:各种遍历形式输出均用空格隔开,删除结点时,若成功,打印成功信息,若失败,则打印失败的信息。程序所能达到的功能程序里面的函数可以实现平衡二叉树的以下功能: 插入新结点前序、中序、后序遍历二叉树前序、中序、后序遍历的非递归算法层次遍历二叉树在二叉树中查找给定关键字交换各结点的左右子树求二叉树的深度叶子结点数删除某结点解题思路插入的思路:插入基于一般二叉排序树的插入,但在插入的同时考虑是否破坏平衡。在结构体中假如balancefunction,来记录当前结点的平衡情况。删除的思路:在删除结点的时候,删除之前先考虑删除之后是否影响该子树的平衡结构,再回溯考虑是否影响整棵AVL树的平衡。调整后再删除。遍历的思路:非递归的遍历都用了栈作为辅助的结构,在树的结点中加入状态来记录当前结点的访问状态。然后再做对应操作。统计深度和叶节点数量的思路:都是用了递归的思想,统计深度是递归求左右子树的深度,取较大值。统计叶节点则是递归求左右子树的叶节点,最后求和。调试分析困难和解决:由于在课本上没有删除的相关算法,一开始要考虑删除后的平衡问题确实比较困难,不过通过上网查找相关资料。最终还是得以解决。同样,非递归遍历的算法也如此,一开始感觉无从下手,不过结合了堆栈的知识之后,就迎刃而解了。使用的测试数据: 第一组:输入顺序是54321,树的三种遍历是42135,12345,。删除结点5后是2143,1234,。第二组:输入顺序是,树的三种遍历是,,.删除结点7后是,,。第三组:,,.删除60后是,,. 算法的效率分析和改进设想:删除和插入的算法均是用了二叉排序树的性质来进行,故算法的效率大概为O(lgn)。而遍历的非递归算法均是以栈结构实现。故应该以O(n)的效率进行。由于算法设计的不完善,删除和插入函数的旋转操作都可以进一步提升效率,判断情况也可以尽量减少冗余。这样可以让时间复杂度前面的系数变小,从而提高算法整体效率。经验和体会: 这次的实验让我充分认识了AVL树的各种操作,及其优越的查找删除效率。但由于一开始对删除操作的不熟悉,走了不少弯路,在上网查找了资料之后阔然开朗。并实现了算法。这次实验的最大体会是,要从小的例子开始,多动手来实际演算算法进行过程,从而发现错误所在。附录--带注释的源程序#include#include#defineLH1 #defineEH0#defineRH-1 #defineWH//printf("