二叉排序树的定义:指一棵空的二叉树,或者是一棵具有如下特征的非空二叉树:
(1)    若它的左子树非空,则左子树上所有结点的值均小于根结点的值;
(2)    若它的右子树非空,则右子树上所有结点的值均大于根结点的值;
(3)    左、右子树本身又各是一棵二叉排序树;
2.在二叉排序树b中查找x的过程:
(1)    若b是空树,则搜索失败,否则
(2)    若x等于b的根结点,则查找成功;否则
(3)    若x小于b的根结点,则搜索左子树;否则
(4)    查找右子树。
3.二叉查找树的生成:
向一个二叉排序树b插入结点s:
(1)    若b 是空树,则将s所指结点作为根结点插入;否则
(2)    若s->data等于b的根结点,则返回;否则
(3)    若s->data小于b的根结点,则把s插入到左子树中;否则
(4)    把s插入到右子树中。
 4.二叉排序树的删除
(1)    首先查找值为s的结点p。
(2)    若p所指结点有左子树,则在其左子树中找到最右结点r来替代被删的结点(即将r所指结点的右指针置成p所指结点的右子树的根,然后用p所结点的左子树的根结点代替被删的p所指结点。
要求:生成一棵二叉排序树(随意放上5个结点),能删除其中任意一个结点,或者能任意再插入一个结点。