二叉排序树与平衡二叉排序树基本操作的实现

《二叉排序树与平衡二叉排序树基本操作的实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、课程设计（论文）编号：B04900083学号：201440410208课程设计教学院计算机学院课程名称数据结构与算法题目二叉排序树与平衡二叉排序树基本操作的实现专业计算机科学与技术班级二班姓名同组人员指导教师成俊15课程设计（论文）2015年12月27日课程设计任务书2015～2016学年第1学期学生姓名：专业班级：计科二指导教师：成俊工作部门：计算机学院一、课程设计题目:二叉排序树与平衡二叉排序树基本操作二、课程设计内容用二叉链表作存储结构，编写程序实现二叉排序树上的基本操作：以回车('')为输入

2、结束标志,输入数列L,生成二叉排序树T；对二叉排序树T作中序遍历；计算二叉排序树T的平均,输出结果；输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历；否则输出信息“无结点x”；判断二叉排序树T是否为平衡二叉树；再用数列L,生成平衡二叉排序树BT:当插入新元素之后,发现当前的二叉排序树BT不是平衡二叉排序树,则立即将它转换成新的平衡二叉排序树BT；计算平衡的二叉排序树BT的平均查找长度，输出结果。三、进度安排15课程设计（论文）1．分析问题，给出数学模型，选择数据结构.2．设计算

3、法，给出算法描述3．给出源程序清单4.编辑、编译、调试源程序5.撰写课程设计报告四、基本要求编写AVL树判别程序，并判别一个二叉排序树是否为AVL树。二叉排序树用其先序遍历结果表示，如：5，2，1，3，7，8。实现AVL树的ADT，包括其上的基本操作：结点的加入和删除；另外包括将一般二叉排序树转变为AVL树的操作。实现提示主要考虑树的旋转操作。目录一、课程设计题目:二叉排序树与平衡二叉排序树基本操作1二、课程设计内容1三、进度安排1四、基本要求1一、概述31.课程设计的目的32.课程设计的要求3二、总体

4、方案设计4三、详细设计61.课程设计总体思想62.模块划分73.流程图815课程设计（论文）四、程序的调试与运行结果说明9五、课程设计总结14参考文献1415课程设计（论文）一、概述1.课程设计的目的1.充分理解和掌握二叉树、平衡二叉树的相关概念和知识。2.掌握排序二叉树的生成、结点删除、插入等操作过程。3.并实现从键盘上输入一系列数据（整型），建立一棵平衡二叉树。4.任意插入或删除一个结点后判断是否为平衡二叉树。5．将非平衡二叉树转换成平衡二叉树。6.按中序遍历输出这棵平衡二叉树。2.课程设计的要求用

5、二叉链表作存储结构，编写程序实现二叉排序树上的基本操作：以回车('')为输入结束标志,输入数列L,生成二叉排序树T；对二叉排序树T作中序遍历；计算二叉排序树T的平均查找长度,输出结果；输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历；否则输出信息“无结点x”；判断二叉排序树T是否为平衡二叉树；再用数列L,生成平衡二叉排序树BT:当插入新元素之后,发现当前的二叉排序树BT不是平衡二叉排序树,则立即将它转换成新的平衡二叉排序树BT；计算平衡的二叉排序树BT的平均查找长度，输出结

6、果。编写AVL树判别程序，并判别一个二叉排序树是否为AVL树。二叉排序树用其先序遍历结果表示，如：5，2，1，3，7，8。实现AVL树的ADT，包括其上的基本操作：结点的加入和删除；另外包括将一般二叉排序树转变为AVL树的操作。实现提示主要考虑树的旋转操作。15课程设计（论文）二、总体方案设计1）建立二叉排序树，编写二叉排序树T作中序遍历。2）查找删除二叉排序树函数。3）编写判断二叉排序树T是否为平衡二叉树函数，把非平衡二叉排序树转换成平衡二叉排序树。4）编写计算二叉树BT的平均查找长度函数。我负责的是

7、第一部分，二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：1.若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；2.若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；3.它的左、右子树也分别为二叉排序树。以链表存储结构创建二叉排序树，以回车('')为输入结束标志,输入数列L,生成二叉排序树T；对二叉排序树T作中序遍历。中序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则(1)中序遍历左子树（L）；(2)访问根结点（V）；(3)中序遍历右子树（R）。函数1：中序遍历二

8、叉树中序遍历二叉树也采用递归函数的方式，先访问左子树2i,然后访问根结点i,最后访问右子树2i+1.先向左走到底再层层返回，直至所有的结点都被访问完毕。（谢石林）函数2：平均查找长度计算二叉排序树的平均查询长度时，可采用类似中序遍历的递归方式，用s记录总查询长度，j记录每个结点的查询长度，s值初值为0，采用累加的方式最总得到总查询长度s，平均查询长度等于s/i（i为树中结点个数）。（吴进）函数3：查找删除二叉排序树函数输入元素x,查找二叉排