二叉排序树与平衡二叉排序树基本操作的实现 课程设计任务书

课程设计任务书

2015 ～2016 学年第 2 学期

学生姓名： 专业班级： 指导教师： 工作部门：

一、课程设计题目: 二叉排序树与平衡二叉排序树基本操作 二、课程设计内容

用二叉链表作存储结构，编写程序实现二叉排序树上的基本操作：以回车('\\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树的操作。

实现提示主要考虑树的旋转操作。