二叉排序树基本操作的实现，它的总结与展望要怎么写
树的应用：二叉排序树
排序是一种十分重要的运算。所谓排序就是把一堆杂乱无章的元素按照某种次序排列起来，形成一个线性有序的序列。二叉排序树是利用二叉树的结构特点来实现对元素排序的。
一、二叉排序树的定义
二叉排序树或者是空树，或者是具有如下性质的二叉树：
1、左子树上所有结点的数据值均小于根结点的数据值；
2、右子树上所有结点的数据值均大于或等于根结点的数据值；
3、左子树、右子树本身又各是一棵二叉排序树。
由此可见，二叉排序树是一种特殊结构的二叉树。（18（10（3，15（12，15）），21（20，21（，37））））就是一棵二叉排序树。
思考题1：试将上述括号表示法表示的二叉排序树...全部
树的应用：二叉排序树
排序是一种十分重要的运算。所谓排序就是把一堆杂乱无章的元素按照某种次序排列起来，形成一个线性有序的序列。二叉排序树是利用二叉树的结构特点来实现对元素排序的。
一、二叉排序树的定义
二叉排序树或者是空树，或者是具有如下性质的二叉树：
1、左子树上所有结点的数据值均小于根结点的数据值；
2、右子树上所有结点的数据值均大于或等于根结点的数据值；
3、左子树、右子树本身又各是一棵二叉排序树。
由此可见，二叉排序树是一种特殊结构的二叉树。（18（10（3，15（12，15）），21（20，21（，37））））就是一棵二叉排序树。
思考题1：试将上述括号表示法表示的二叉排序树用图形表示法表示出来。
图
思考题2：试用中序遍历二叉树的方法写出遍历二叉排序树的结果，并思考二叉排序树究竟有什么作用？。
二、二叉排序树的构造
二叉排序树的构造过程实质上就是排序的过程，它是二叉排序树作媒介，将一个任意的数据序列变成一个有序序列。
二叉排序树的构造一般是采用陆续插入结点的办法逐步构成的。具体构造的思路是：
1、以待排序的数据的第一个数据构成根结点；
2、对以后的各个数据，逐个插入结点，而且规定：在插入过程的每一步，原有树结点位置不再变动，只是将新数据的结点作为一个叶子结点插入到合适的位置，使树中任何结点的数据与其左、右子树结点数据之间的关系仍然符合对二叉排序树的要求。
思考题3：试根据上述构造二叉排序树的思路，画出待排序数据（50，54，71，23，48，55，79，32，21）的二叉排序树图。
总结：构造二叉排序树的算法思想如下：设A={a1,a2,。
。。,an}为一组元素的集合，
1、令a1为二叉排序树的根；
2、在保持二叉排序树性质的前提下，依次把a2,a3,。。。,an插入到该树中。
二叉排序树的生成算法：
Procedure createbst(Var t:pointer);
{构造一棵以t指向根结点的二叉排序树，插入数据以‘#’结束}
Begin
t:=nil; {初始化}
read(x); {输入元素值x}
while (x<>'#') do
begin
new(s);s^。
Lc:=nil;s^。Rc:=nil;
s^。data:=x;
insertnode(s,t);
read(x)
end;
end。
其中，插入一个结点的算法insertnode(s，t)如下：
Procedure insertnode(s:pointer;Var t:pointer);
{s指向待插入结点，t是bst的根}
Begin
if t=nil then t:=s
else if s^。
data < t^。data then insertnode(s,t^。Lc)
else insertnode(s,t^。Rc)
end。
注意该算法为尾递归算法。不用栈即可转为非递归。
思考题4：试用Pascal语言编写一个程序，实现对未排序数据的输入、排序和输出排序结果。（要求应用二叉排序树）标准程序 参考程序（黄硕）
思考题5：假设已经生成了一棵二叉树，试按照二叉排序树的思想设计一个算法，判断这棵二叉树是否为二叉排序树。
收起
