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

编号：B04900083

学号：8 Array课程设计

教学院计算机学院

课程名称数据结构与算法

题目二叉排序树与平衡二叉排序树基本操

作的实现

专业计算机科学与技术

班级二班

姓名

同组人员

指导教师成俊

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的平均查找长度，输出结果。

编写A VL树判别程序，并判别一个二叉排序树是否为A VL树。二叉排序树用其先序遍历结果表示，如：5，2，1，3，7，8。

实现A VL树的ADT，包括其上的基本操作：结点的加入和删除；另外包括将一般二叉排序树转变为A VL树的操作。

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

二、总体方案设计

1）建立二叉排序树，编写二叉排序树T作中序遍历。

2）查找删除二叉排序树函数。

3）编写判断二叉排序树T是否为平衡二叉树函数，把非平衡二叉排序树转换成平衡二叉排序树。

4）编写计算二叉树BT的平均查找长度函数。

我负责的是第一部分，二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

1.若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

2.若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

3.它的左、右子树也分别为二叉排序树。

以链表存储结构创建二叉排序树，以回车('\n')为输入结束标志,输入数列L,生成二叉排序树T；对二叉排序树T作中序遍历。

中序遍历二叉树算法的框架是：若二叉树为空，则空操作；

否则(1)中序遍历左子树（L）；

(2)访问根结点（V）；

(3)中序遍历右子树（R）。

函数1：中序遍历二叉树

中序遍历二叉树也采用递归函数的方式，先访问左子树2i,然后访问根结点i,最后访问右子树2i+1.先向左走到底再层层返回，直至所有的结点都被访问完毕。

（石林）函数2：平均查找长度

计算二叉排序树的平均查询长度时，可采用类似中序遍历的递归方式，用s记录总查询长度，j记录每个结点的查询长度，s值初值为0，采用累加的方式最总得到总查询长度s，平均查询长度等于s/i（i为树中结点个数）。

（吴进）函数3：查找删除二叉排序树函数

输入元素x,查找二叉排序树T,若存在含x的结点,则删该结点,并作中序遍历(执行函数1)；否则输出信息“无x”。

（常勋）函数4：判断二叉排序树T是否为平衡二叉树，若不是则用数列L，生成平衡排序二叉树BT；最后调用函数6 ，接着调用函数5.判断二叉排序树是否为平衡二叉树的函数也是采用递归函数的方式，分别判定以树中每个节点为