二叉排序树（BST），也称二叉查找树。
二叉排序树或者为空树，或者为非空树，当为非空树时有如下特点：
1、若左子树非空，则右子树所有的结点关键字值均小于根节点的关键字。
2、若右子树非空，则右子树所有的结点关键字值均大于根节点的关键字。
3、左、右子树本身也分别是一课二叉排序树。
* 二叉排序树的中序遍历序列是一个递增的有序序列。
查找
二叉树非空时，查找根结点，若相等则查找成功；
若不等，则当小于根节点值时，查找左子树；当大于根节点值时，查找右子树。
当查找到叶子结点仍没查找到相应的值，则查找失败。
BSTNode *BST_Search(BiTree T,ElemType key,BSTNode *&p){
p=null;
while(T!=null&key!=T->data){
p=T;
if(key>T->data)
T = T->rchild;
else
T = T->lchild;
}
return T;
}
插入
如二叉排序树为空，直接插入结点；
若二叉排序树非空，当值小于根结点的时，插入左子树；当值大于根结点时，插入右子树；当值等于根结点时不进行插入。
int BST_Insert(BiTree &T,KeyType k){
if(T==NULL)
T = (BiTree)malloc(sizeof(BSTNode));
T->date = k;
T->lchild = T->rchild = null;
return 1;
else if(T->data==k)
return 0;
else if( k > T->data )
return BST_Insert(T->rchild,k);
else
return BST_Insert(T->lchild,k);
}
构造二叉排序树
读入一个元素并建立结点，若二叉树为空，将其作为根结点；
若二叉树排序树非空，当值小于根结点时，插入左子树；当值小于根结点时，插入右子树；当值等于根结点时，不进行插入。
void Create_BST(BiTree &T,KeyType str[],int n){
T=NULL;
int i = 0;
while(i<n){
BST_Insert(T,str[i]);
i++;
}
}
注：二叉排序树的构建情况会因为str数组中数字排序的顺序不一样，而产生不一样的效果。
删除
1、若被删除的结点是叶子结点，则直接删除；
2、若被删除结点z只有一棵子树，则让z的子树成为z父结点的子树，代替z结点；
3、若被删除的结点z有两棵子树，则让z的中序序列直接后继代替z，并删去直接后继结点。
在二叉排序树中删除并插入某结点（结点值相同），得到的二叉排序树是否与原来一致？
结论：可能相同，也可能不同。
查找效率
平均查找长度(ASL)取决于树的高度。
