二叉排序树

二叉排序树（Binary Sort Tree）又称为二叉搜索树、二叉查找树
定义：二叉排序树或是空树，或是满足如下性质的二叉树：
（1）若其左子树非空，则左子树上所有结点的值均小于根结点的值
（2）若其右子树非空，则右子树上所有结点的值均大于等于根结点的值
（3）其左右子树本身又各是一棵二叉排序树
二叉排序树的性质：
中序遍历非空的二叉排序树所得到的数据元素排列是一个按关键字排列的递增有序序列
二叉排列树的操作——查找
（1）若查找的关键字等于根结点，成功
（2）否则
①若小于根结点，查其左子树
②若大于根结点，查其右子树
（3）在左右子树上的操作类似
二叉排序树的存储结构
typedef struct{
KeyType key; //关键字项
InfoType otherinfo; //其他数据域
}ElemType;
typedef struct BSTNode{
ElemType data; //数据域
struct BSTNode lchild, rchild; //左右孩子指针
}BSTNode, *BSTree;
BSTree T; //定义二叉排序树T
二叉排序树的递归查找
算法思想：
（1）若二叉排序树为空，则查找失败，返回空指针
（2）若二叉排序树非空，将给定值key与根结点的关键字T->data.key进行比较：
①若key等于T->data.key，则查找成功，返回根结点地址
②若key小于T->data.key，则进一步查找左子树
③若key大于T->data.key，则进一步查找右子树
算法描述：
BSTree SearchBST(BSTree T,KeyType key){
if((!T)||key==T->data.key) return T;
else if(keydata.key)
return SearchBST(T->data.key); //在左子树中继续查找
else return SerachBST(T->data.key); //在右子树中继续查找
}
二叉排序树的查找分析：
二叉排序树上查找某关键字等于给定值的结点过程，其实就是自乐一条从根到改结点的路径
比较的关键字次数=此结点所在层次数
最多的比较次数=树的深度
二叉排序树的操作——插入
（1）若二叉排序树为空，则插入结点作为根结点插入到空树中
（2）否则，继续在其左、右子树上查找
1）树中已有，不再插入
2）树中没有，查找直至某个叶子结点的左子树或右子树为空为止，则插入结点应为改叶子结点的左孩子或右孩子
二叉排序树的操作——生成
从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树
一个无序序列可通过构造二叉排序树而变成一个有序序列，构造树的过程就是对无序序列进行排序的过程
插入的结点均为叶子结点，故无需移动其他结点，相当于在有序序列上插入记录而无需移动其他记录，但是关键字的输入顺序不同，建立的二叉排序树不同
二叉排序树的操作——删除
从二叉排序树中删除一个结点，不能把以该结点为根的子树都删去，只能删掉该结点，并且还应保证删除后所得到的二叉树仍然满足二叉排序树的性质不变
由于中序遍历二叉排序树可以得到一个递增有序的序列，那么，在二叉排序树中删去一个结点相当于删去有序序列中的一个结点：
①将因删除结点而断开的二叉链表重新链接起来
②防止重新链接后的树的高度增加
（1）被删除的结点是叶子结点：直接删去该结点
（2）被删除的结点只有左子树或者右子树，用其左子树或者右子树替换它（结点替代）
（3）被删除的结点既有左子树，也有右子树
以其中序前趋值替换之（值替换），然后再删除该前趋结点，前趋是左子树中最大的结点
也可以是用后继替换之，然后再删除该后继结点，后继是右子树中最小的结点