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

编 号： 学 号： 201440410208 课 程 设 计 教 学 院 计算机学院 课程名称 数据结构与算法 题 目 二叉排序树与平衡二叉排序树基本操作的实现 专 业 计算机科学与技术 班 级 二班 姓 名 同组人员 指导教师 成俊 2015 年 12 月 27 日 课程设计任务书 2015 ～2016 学年 第 1 学期 学生姓名： 专业班级： 计科二 指导教师： 成俊 工作部门： 计算机学院 一、课程设计题目: 二叉排序树与平衡二叉排序树基本操作 二、课程设计内容 用二叉链表作存储结构，编写程序实现二叉排序树上的基本操作：以回车(\n)为输入结束标志,输入数列L,生成二叉排序树T；对二叉排序树T作中序遍历；计算二叉排序树T的平均,输出结果；输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历；否则输出信息“无结点x”； 判断二叉排序树T是否为平衡二叉树；再用数列L,生成平衡二叉排序树BT:当插入新元素之后,发现当前的二叉排序树BT不是平衡二叉排序树,则立即将它转换成新的平衡二叉排序树BT；计算平衡的二叉排序树BT的平均查找长度，输出结果。 三、进度安排 1．分析问题，给出数学模型，选择数据结构. 2．设计算法，给出算法描述 3．给出源程序清单 4. 编辑、编译、调试源程序 5. 撰写课程设计报告 四、基本要求 编写AVL树判别程序，并判别一个二叉排序树是否为AVL树。二叉排序树用其先序遍历结果表示，如：5，2，1，3，7，8。 实现AVL树的ADT，包括其上的基本操作：结点的加入和删除；另外包括将一般二叉排序树转变为AVL树的操作。 实现提示主要考虑树的旋转操作。 目录 一、课程设计题目: 二叉排序树与平衡二叉排序树基本操作 1 二、课程设计内容 1 三、进度安排 1 四、基本要求 1 一、概述 3 1.课程设计的目的 3 2.课程设计的要求 3 二、总体方案设计 4 三、详细设计 6 1.课程设计总体思想 6 2.模块划分 7 3.流程图 8 四、程序的调试与运行结果说明 9 五、课程设计总结 14 参考文献 14 一、概述 1.课程设计的目的 1.充分理解和掌握二叉树、平衡二叉树的相关概念和知识。 2.掌握排序二叉树的生成、结点删除、插入等操作过程。 3.并实现从键盘上输入一系列数据（整型），建立一棵平衡二叉树。 4.任意插入或删除一个结点后判断是否为平衡二叉树。 5．将非平衡二叉树转换成平衡二叉树。 6.按中序遍历输出这棵平衡二叉树。 2.课程设计的要求 用二叉链表作存储结构，编写程序实现二叉排序树上的基本操作：以回车(\n)为输入结束标志,输入数列L,生成二叉排序树T；对二叉排序树T作中序遍历；计算二叉排序树T的平均查找长度,输出结果；输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历；否则输出信息“无结点x”； 判断二叉排序树T是否为平衡二叉树；再用数列L,生成平衡二叉排序树BT:当插入新元素之后,发现当前的二叉排序树BT不是平衡二叉排序树,则立即将它转换成新的平衡二叉排序树BT；计算平衡的二叉排序树BT的平均查找长度，输出结果。 编写AVL树判别程序，并判别一个二叉排序树是否为AVL树。二叉排序树用其先序遍历结果表示，如：5，2，1，3，7，8。 实现AVL树的ADT，包括其上的基本操作：结点的加入和删除；另外包括将一般二叉排序树转变为AVL树的操作。 实现提示主要考虑树的旋转操作。 二、总体方案设计 建立二叉排序树，编写二叉排序树T作中序遍历。 查找删除二叉排序树函数。 编写判断二叉排序树T是否为平衡二叉树函数，把非平衡二叉排序树转换成平衡二叉排序树。 编写计算二叉树BT的平均查找长度函数。 我负责的是第一部分，二叉排序树或者是一棵空树，或者是具有下列性质的二叉树： 1.若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 2.若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 3.它的左、右子树也分别为二叉排序树。 以链表存储结构创建二叉排序树，以回车(\n)为输入结束标志,输入数列L,生成二叉排序树T；对二叉排序树T作中序遍历。 中序遍历二叉树算法的框架是：若二叉树为空，则空操作； 否则(1)中序遍历左子树（L）； (2)访问根结点（V）； (3)中序遍历右子树（R）。 函数1：中序遍历二叉树 中序遍历二叉树也采用递归函数的方式，先访问左子树2i,然后访问根结点i,最后访问右子树2