课程设计报告
设计题目：二叉排序树与平衡二叉树的实现
专 业 班 级 学 生 学 号 指导教师 起止时间
年 学期
1/18
目 录
1.需求分析： ........................................ 3 1.1课程设计题目、任务及要求： ......... 3 1.2课程设计思想： ................................. 3 2.概要设计： ........................................ 5 2.1二叉排序树的定义： ......................... 5 2.2二叉排序的存储结构： ..................... 5 2.3模块划分： ......................................... 5 2.4主函数流程图： ................................. 6 3.详细设计和代码： .............................. 8 3.1二叉链表： ......................................... 8 3.2顺序表： ........................................... 14 4.心得与体会： ................................... 18
2/18
1.需求分析：
1.1课程设计题目、任务及要求：
用二叉链表作存储结构：
(1)以回车('\\n')为输入结束标志,输入数列L，生成一棵二叉排序树T；
(2)对二叉排序树T作中序遍历，输出结果；
(3)计算二叉排序树T查找成功的平均查找长度,输出结果； (4)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；
用顺序表(一维数组)作存储结构：
(1)以回车('\\n')为输入结束标志,输入数列L，生成一棵二叉排序树T；
(2)对二叉排序树T作中序遍历,输出结果；
(3)计算二叉排序树T查找成功的平均查找长度,输出结果； (4)输入元素x,查找二叉排序树T:若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；
1.2课程设计思想： 生成二叉排序树：
建立二叉排序树采用的是边查找边插入的方式。查找函数采用递归的方式进行查找。查找是按照二叉排序树的性质进行的，通过比较
3/18
要插入元素的关键字与当前结点关键字的大小来决定我们是遍历当前结点的哪个子树。如果小于当前结点关键字，则遍历它的左子树；大于当前结点关键字，则遍历它的右子树；等于当前关键字，则此元素不插入原树。我们按照这样的规律，一直向下遍历，知道它的子树为空，则返回当前结点的上一个结点。然后利用插入函数将该元素插入原树。 中序遍历：
对二叉排序树进行中序遍历采用递归函数的方式。在根节点不为空的情况下，先访问左子树，在访问根结点，最后访问右子树。 平均查找长度：
计算二叉排序树的平均查找长度，仍采用类似中序遍历的递归方式，用s记录总查找长度，j记录每个结点的查找长度，s置初值为0，采用累加的方式最终得到总查找长度s，平均查找长度就等于s/j（i为树中结点的总个数）。 删除结点：
删除结点函数，采用边查找变删除的方式。如果没有查找到，则不对树做任何的修改：如果查找到结点，则分四种情况分别进行讨论：
（1） 该结点左右子树均为空； （2） 该结点仅左子树为空； （3） 该结点仅右子树为空； （4） 该结点左右子树都不为空；
4/18
2.概要设计：
2.1二叉排序树的定义：
二叉排序树是一种动态树表。二叉排序树的定义：二叉排序树或者是一棵空树，或者是一棵具有如下性质的二叉树：
（1）每个结点都有一个作为搜索依据的关键字（key），所有结点的关键字互不相同。
（2）若它的左子树非空，则左子树上所有结点的值均小于根节点的值；
（3）若它的右子树非空，则右子树上所有结点的值均大于根节点的值；
（4）左、右子树本身又各是一棵二叉排序树。
2.2二叉排序的存储结构： 二叉链表：
建二叉树的结点应该包含三个域，分别存放结点的数据域data。左孩子结点指针leftChild和右孩子结点指针rightChild。 顺序表：
顺序表中应该包含一个数组指针（动态申请空间）和一个记录数组长度的size。
2.3模块划分： 二叉链表：
5/18