1 课 程 设 计 课程名称 数据结构课程设计 题目名称 二叉排序树的实现 学生学院 应用数学学院 专业班级 信息计算 1 班 学 号 ********** 学生姓名 陈辉腾 指导教师 刘志煌 2016 年 6 月 27 日 2 二叉排序树的实现 应 数 14信计1班 3114008104 陈辉腾 课程设计要求： 二叉排序树的实现 二叉排序补充概念(也可以参考书上第九章第二节) 左子树的数据总是小于根和右子树的数据,这种就叫做二叉排序树,简单一点,二叉排序树左边的数据小于右边. 1）编程实现二叉排序树， 包括生成、插入，删除； 2）对二叉排序树进行先根、中根、 和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 例如,a 为根,左右孩子是 bc,b 的孩子是 de,c 的孩子是 fg. 也可以像这样更加美观: 也可以是竖着显示,a 为根,bc 为孩子. 4）分别用二叉排序树和数组去存储一个班(50 人以上)的成员信息(至少包括学号、姓名、成绩 3 项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 5） 格式就要按照我们作业的要求,对数据测试,分析,总结 和改进的工作要做的详细一点。 3 1 、编程实现二叉排序树， 包括生成、插入、删除； 1.1 数据类型定义 1.2 生成一颗二叉排序树 方法一：手工输入，递归生成。 生成一颗二叉排序树如下： 这样生成一棵二叉排序树，就是要自己判断每个结点应该放在什么地方，因为二叉排序树规定了二叉排序树左边的数据小于右边。显然，这样每次构建一棵二叉排序树都需要事先规定好一个数据元素序列，然后依次输入。这样的弊端就是你不细心一点就有可能构建出一棵错误的二叉排序树——非二叉排序树。优点就是可以构建自己想要的二叉排序树。 4 方法二：随机生成。 这里用到了C++里面的rand()函数，用于生成大于等于0的伪随机数(每次运行产生的随机数都是固定的)。用这个函数需要使用名字空间using namespace std;同时引进#include。 思路是：按依次插入结点来生成一棵二叉排序树，在插入函数里进行判断：即编写生成二叉排序树的规则。另外，事先要有一堆结点（用于生成二叉排序树），我是事先保存在一个数组里。然后每次产生一个伪随机数（范围是0到数组长度）作为数组下标，并把对应的该下标的数组元素插入到要生成的二叉排序树里。 其中for循环次数就是生成二叉排序树结点个数的最大值减1。最大是因为产生的伪随机...
