合肥学院 计算机科学与技术系 课程设计报告 2 0 0 9 ～2 0 1 0 学年第 二 学期 课程 数据结构与算法 课程设 计 名 称 二叉排序树运算 学生姓名 顾成方 学号 0 7 0 4 0 1 1 0 3 3 专业班级 08 计科(2) 指导教师 王昆仑 张贯虹 2010 年 5 月 题目：（二叉排序树运算问题）设计程序完成如下要求：对一组数据构造二叉排序树，并在二叉排序树中实现多种方式的查找。基本任务：⑴选择合适的储存结构构造二叉排序树；⑵对二叉排序树T 作中序遍历，输出结果；⑶在二叉排序树中实现多种方式的查找，并给出二叉排序树中插入和删除的操作。⑷尽量给出“顺序和链式”两种不同结构下的操作，并比较。 一、 问题分析和任务定义 本次程序需要完成如下要求：首先输入任一组数据，使之构造成二叉排序树，并对其作中序遍历，然后输出遍历后的数据序列；其次，该二叉排序树能实现对数据（即二叉排序树的结点）的查找、插入和删除等基本操作。 实现本程序需要解决以下几个问题： 1、 如何构造二叉排序树。 2、 如何通过中序遍历输出二叉排序树。 3、 如何实现多种查找。 4、 如何实现插入删除等操作。 二叉排序树的定义： ⑴ 其左子树非空，则左子树上所有结点的值均小于根结点的值。 ⑵ 若其右子树非空，则右子树上所有结点的值大于根结点的值。 ⑶ 其左右子树也分别为二叉排序树。 本问题的关键在于对于二叉排序树的构造。根据上述二叉排序树二叉排序树的生成需要通过插入算法来实现：输入（插入）的第一个数据即为根结点；继续插入，当插入的新结点的关键值小于根结点的值时就作为左孩子，当插入的新结点的关键值大于根结点的值时就作为右孩子；在左右子树中插入方法与整个二叉排序树相同。当二叉排序树建立完成后，要插入新的数据时，要先判断已建立的二叉排序树序列中是否已有当前插入数据。因此，插入算法还要包括对数据的查找判断过程。 本问题的难点在于二叉排序树的删除算法的实现。删除前，首先要进行查找，判断给出的结点是否已存在于二叉排序树之中；在删除时，为了保证删除结点后的二叉树仍为二叉排序树，要考虑各种情况，选择正确的方法。删除操作要分几种情况讨论，在后面有介绍。 二、 概要设计和数据结构选择 用二叉链表作为二叉排序树的存储结构，其中key 为结点关键值，*lchlid、*rchild 分别为左右孩子指针。该程序的结构如下图所示： 三、 详细设计和编码 首先定义二...
