数据结构课程设计（1） 作业A
一、大型作业（课程设计）题目和内容
1.1二叉排序树与平衡二叉排序树基本操作的实现 1.用二叉链表作储存结构
（1） （2） （3） （4）
以回车（’n'）为输入结束标志，输入数列 对二叉排序树T作中序遍历，输出结果； 计算二叉排序树T的平均查找长度，输出结果；
输入元素x，查找二叉排序树 T,如果存在含x的结点，则删除该结点，
L,生成二叉排序树 T;
并作中序遍历（执行操作2）;否则输出信息“无结点 x”； （5）
判断二叉排序树T是否为平衡二叉树，输出信息“ 0K!” / “ NO”；
*（6） 再用数列L,生成平衡二叉排序树 BT:当插入新元素后，发现当前二叉排序树
BT；
BT
不是平衡二叉排序树，则立即将它转换成新的平衡二叉排序树
* （ 7） 计算平衡二叉排序树 BT的平均查找长度，输出结果。
2、 用顺序表（一维数组）作存储结构 (1) (2) (3)
以回车（’n'）为输入结束标志，输入数列
L,生成二叉排序树 T；
对二叉排序树T作中序遍历，输出结果；
计算二叉排序树 T的平均查找长度，输出结果； 输入元素x，查找二叉排序树 T,如果存在含x的结点，
则删除该结点，并作中序遍
(4)
历（执行操作2）;否则输出信息“无结点 x”；
（5 ）判断二叉排序树 T是否为平衡二叉树，输出信息“ 0K!” / “ NO”。 二. 程序中所采用的数据结构及存储结构的说明
程序中的数据采用“树形结构”作为其数据结构。
树”。
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若它的左子
具体的，我采用的是“二叉排序
树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若它的右子树不空，则右子
树上所有结点的值均大于它的根结点的值； （3）它的左右子树也分别为二叉排序树。
程序中分别采用了 “二插链表”和“一维数组”作为其存储结构。
二插链表存储结构中二插树的结点由一个数据元素和分别指向其左、右子树的
两个分支构成。如：我的程序中采用的结构是：
typedef struct Tno de{ int data;
struct Tn ode *lchild,*rchild }*n ode,BST node;
；
一维数组顺序表存储结构是用一组地址连续的存储单元依次自上而下、自左而右存
储完全二插树上的结点元素，即将完全二叉树上编号为 数组中下标为i-1的分量中。利用顺序表作为存储结构：
i的结点元素存储在如上定义的一维
typedef struct { int *data; int len th; }BST;
一维数组存储结构中结点
三. 算法的设计思想
i的父母亲为|_i/2」，左孩子为2i，右孩子为2i+1.
a）二插链表作存储结构：
建立二插排序树采用边查找边插入的方式。
如果查找成功则不应再插入原树， 元素插入原树。
对二叉树进行 中序遍历采用递归函数的方式。
子树，再访问根结点，最后访问右子树。
查找函数采用递归的方式进行查找。
然后利用插入函数将该
否则返回当前结点的上一个结点。
在根结点不为空的情况下， 先访问左
计算二插排序树的平均查找长度时，仍采用类似中序遍历的递归方式， 用s记录
二叉树与平衡二叉树实现资料讲解
