1.二叉排序树的定义
二叉排序树，又称二叉查找数树，一颗二叉树或者是空二叉树，或者是具有如下性质的二叉树：
a.左子树上所有结点的关键字均小于根结点的关键字；
b.右子树上所有结点的关键字竣大雨根结点的关键字。
c.左子树和右子树又各是一颗二叉排序树。
——>左子树结点值<根结点值<右子树结点值
进行中序遍历，可以得到一个递增的有序遍历
代码如下：
//二叉排序树结点
typedef struct BSTNode{
int key;
struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;
//在二叉排序树中查找值为key的结点
BSTNode *BST_Search(BSTree T, int key){
while(T!=NULL&&key!=T->key){ //若树空或等于根结点值，则结束循环
if(key<T->key) T=T->lchild; //小于，则在左子树上查找
else T=T->rchild; //大于，则在右子树上查找
}
return T;
}
2.二叉排序树的查找
若树非空，目标值与跟结点比较：
a.若相等，则查找成功
b.若小于跟结点，则在左子树上查找，否则在右子树上查找。
c.查找成功，返回结点指针：查找失败返回NULL
代码如下：
//二叉排序树结点
typedef struct BSTNode{
int key;
struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;
//在二叉排序树中序寻找值为key的结点（非递归）
BSTNode *BST_Search(BSTree T, int key){
while(T!=NULL&&key!=T->key){ //若树空或等于根结点值，则结束循环
if(key<T->key) T=T->lchild; //小于，则在左子树上查找
else T=T->rchild; //大于，则在右子树上查找
}
return T;
}
//在二叉排序树中查找值为key的结点（递归）
BSTNode *BSTSearch(BSTree T, int key){
if(T==NULL)
return NULL;
if(key==T->key)
return T;
else if(key<T->key)
return BSTSearch(T->lchild, key); //在左子树中找
else
return BSTsearch(T->rchild, key); //在右子树中找
}
3.二叉排序树的插入
若二叉排序树为空，则直接插入结点；否则，若关键字k小雨根结点值，则插入到左子树，若关键字k大于根结点值，则插入到右子树
代码如下：
//在二叉排序树插入关键字为k的新结点（递归实现）最坏空间复杂度为O(h)
int BST_Insert(BSTree &T, int k){
If(T==NULL){
T=(BSTree)malloc(sizeof(BSTNode));
T->key=k;
T->lchild=T->rchild=NULL;
return 1; //返回1，插入成功
}
else if(k==T->key) //树中存在相同关键字的结点，插入失败
return 0;
else if(k<T->key) //插入到T的左子树
return BST_Insert(T->lchild, k);
else //插入到T的右子树
return BST_insert(T->rcild, k);
}
4.二叉排序树的构造
//按照str[]中的关键字序列建立二叉排序树
void Creat_BST(BSTree &T, int str[], int n){
T=NULL; //初始时T为空树
int i=0;
while(i<n){ //依此将每个关键字插入到二叉排序树中
BST_Insert(T,str[i];
i++;
}
}
结论：
不同的关键字序列可能得到同款二叉排序树，也可能得到不同款二叉排序树
5.二叉排序树的删除
先搜索目标结点：
a.若被删除结点z是叶结点，则直接删除，不会破坏二叉排序树的性质
b.若结点z只有一个左子树或右子树，则让z的子树成为z父结点的子树，替代z的位置
c.若结点z有左、右两棵子树，则令z的直接后继（或直接前驱）替代z，然后从二叉排序树中删去这个直接后继（或直接前驱），这样就转换成了第一或第二种情况。
z的后继：z的右子树最左下结点（该结点一定没有左子树）
z的前驱：z的左子树最右下结点（该结点一定没有右子树）
6.查找 效率分析
查找长度—-在查找运算中，需要对比关键字的次数称为查找长度，反映了查找操作时间复杂度。
平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过1。
n个结点的二叉树最小高度为⌊log2 n⌋+1（完全二叉树）而平衡二叉树高度与完全二叉树同等数量级。
总结：查找效率取决于树的高度，最好O(log2n),最坏O(n),查找失败的情况(需补充失败结点)