1、二叉搜索树是二叉树的一种，树的每个结点含有一个数据项，每个数据项有一个键值。结点的存储位置是由键值的大小决定的，所以二叉搜索树是关联式容器。
(1)、 若它的左子树不空，则左子树上所有结点的键值均小于它的根结点的键值；
(2)、若它的右子树不空，则右子树上所有结点的键值均大于它的根结点的键值；
(3)、它的左、右子树也分别为二叉排序树。
注意：：：二叉排序树是一种动态树表，树的结构通常不是一次生成的。而是在查找的过程中，当树中不存在关键字等于给定值的节点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。

2、插入与查找算法：
查找：
（1）、若二叉排序树非空，将给定值与根节点的关键字值比较，若相等，则查找成功；
（2）、若不等，则当根节点的关键字值大于给定值时，到根的左子树中进行查找；
（3）、否则到根的右子树中进行查找。若找到，则查找过程是走了一条从树根到所找到节点的路径；
（4）、否则，查找过程终止于一棵空树。
//① 、普通查找，查找不成功返回NULL
递归思想：
 BiTree SearchBST (BiTree *T，KeyType key)
{
    //在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素
    //若查找成功，则返回指向该数据元素结点的指针，否则返回空指针
        if( (!T)||(key==T—>data.key))
            return (T)； //查找结束,此时T为NULL，或者为该结点
        else if (key< T—>data.key)
                return(SearchBST(T—>lchild，key))； //在左子树中继续查找
                else
                return(SearchBST(T —>rchild，key))；// 在右子树中继续查找
    }//SearchBST

非递归思想：
BiTree SearchBST (BiTree *root，KeyType key)
{ 
   BiTree *p；
   if( root ＝＝ NULL)return NULL；//查找结束,此时根为NULL，
   p ＝ root；
   while(p!=NULL)
   { 
        if(p －>key==Key)breat；
       if( Key < p ->key) p ＝p －>lchild；//在左子树中继续查找
         else p ＝ p －>rchild；//在右子树中继续查找
    }
   return p；
}
//② 、查找不成功，返回插入位置
    //在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素，
    //若查找成功，则指针p指向该数据元素结点，并返回TRUE，
    //否则指针p指向查找路径上访问的最后一个结点并返回FALSE，
    //指针f指向T的双亲，其初始调用值为NULL
 BOOL SearchBST(BiTree *T，KeyType key，BiTree *f，BiTree &p)
{
        if(!T) {p=f；return FALSE；} //查找不成功
        else if (key==T—>data.key) 
            {p=T；return TRUE；} //查找成功
           else if (key<T—>data.key) SearchBST(T—>lchild，key，T，p)； //在左子树中继续查找
                        else SearchBST(T—>rchild，key，T，p)；//在右子树中继续查找
    }//SearchBST

插入：
（1）、首先执行查找算法，找出被插结点的父亲结点。没找到则新建子结点

（2）、判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。

（3）、若二叉树为空。则首先单独生成根结点

基于BOOL SearchBST(BiTree *T，KeyType key，BiTree *f，BiTree &p)的插入算法
相当于新建子树。
 //当二叉排序树T中不存在关键字等于e.key的数据元素时,插入e并返回TRUE，否则返回FALSE
Status Insert BST(BiTree &T，ElemType e)
{
            if(!SearchBST(T，e.key，NULL，p) ) //返回P为插入的结点点
        { //先查找，不成功新建结点
            s=(BiTree)malloc(sizeof(BiTNode))；
            s->data=e； s->lchild= s->rchild=NULL；
            if (!p) T = s； //被插结点*s为新的根结点 ，原树为空
            else if (e.key<p->data.key) p->lchild=s； //被插结点*s为左孩子
                    else p—>rchild=s //被插结点*s为右孩子
            return TRUE；
          }
        else 
      return FALSE; //树中已有关键字相同的结点，不再插入
    }// Insert BST

  void InsertBST(BSTree *Tptr，KeyType key)
      {
//若二叉排序树 *Tptr中没有关键字为key，则插入，否则直接返回
        BSTNode *f，*p=*TPtr； //p的初值指向根结点
        while(p){ //查找插入位置
          if(p->key==key) return；//树中已有key，无须插入
          f=p； //f保存当前查找的结点
          p=(key<p->key)?p->lchild：p->rchild；
            //若key<p->key，则在左子树中查找，否则在右子树中查找
         } //endwhile
         //f为插入的结点
        p=(BSTNode *)malloc(sizeof(BSTNode))；
        p->key=key； p->lchild=p->rchild=NULL； //生成新结点
        if(*TPtr==NULL) //原树为空
           *Tptr=p； //新插入的结点为新的根
        else //原树非空时将新结点关p作为关f的左孩子或右孩子插入
          if(key<f->key)
            f->lchild=p；
          else f->rchild=p；
       } //InsertBST

4、删除算法
①删除操作的一般步骤
(1) 进行查找
    　查找时，令p指向当前访问到的结点，parent指向其双亲(其初值为NULL)。若树中找不到被删结点则返回，否则被删结点是*p。
(2) 删去*p。
    　删*p时，应将*p的子树(若有)仍连接在树上且保持BST性质不变。按*p的孩子数目分三种情况进行处理。

②删除*p结点的三种情况
(1)*p是叶子(即它的孩子数为0)
    　无须连接*p的子树，只需将*p的双亲*parent中指向*p的指针域置空即可。

(2)*p只有一个孩子*child
    　只需将*child和*p的双亲直接连接后，即可删去*p。
  注意：
    　*p既可能是*parent的左孩子也可能是其右孩子，而*child可能是*p的左孩子或右孩子，故共有4种状态。
(3)*p有两个孩子
    　先令q=p，将被删结点的地址保存在q中；然后找*q的中序后继*p，并在查找过程中仍用parent记住*p的双亲位置。*q的中序后继*p一定是*q的右子树中最左下的结点，它无左子树。因此，可以将删去*q的操作转换为删去的*p的操作，即在释放结点*p之前将其数据复制到*q中，就相当于删去了*q。
③二叉排序树删除算法
分析：
    　上述三种情况都能统一到情况(2)，算法中只需针对情况(2)处理即可。
    　注意边界条件：若parent为空，被删结点*p是根，故删去*p后，应将child置为根。


算法：删除关键字为key的结点
void DelBSTNode(BSTree *Tptr，KeyType key)
 {
//在二叉排序树*Tptr中删去关键字为key的结点
  BSTNode *parent=NUll，*p=*Tptr，*q，*child；
  while(p)
{ 
     //从根开始查找关键字为key的待删结点
    if(p->key==key) break；//已找到，跳出查找循环
    parent=p； //parent指向*p的双亲
    p=(key<p->key)?p->lchild：p->rchild； //在关p的左或右子树中继续找
 } 
//注意：也可以使用基于BOOL SearchBST(BiTree *T，KeyType key，BiTree *f，BiTree &p)的查找算法
//结果是  parent 记录了要删除结点的父结点，p指向要删除的结点

      if(!p) return； //找不到被删结点则返回
     q=p； //q记住被删结点*p
     if(q->lchild && q->rchild) //*q的两个孩子均非空，故找*q的中序后继*p
    for(parent=q，p=q->rchild； p->lchild； parent=p，p=p=->lchild)；
  //现在情况(3)已被转换为情况(2)，而情况(1)相当于是情况(2)中child=NULL的状况
    child=(p->lchild)?p->lchild：p->rchild；//若是情况(2)，则child非空；否则child为空
    if(!parent) //*p的双亲为空，说明*p为根，删*p后应修改根指针
      *Tptr=child； //若是情况(1)，则删去*p后，树为空；否则child变为根
    else{ //*p不是根，将*p的孩子和*p的双亲进行连接，*p从树上被摘下
      if(p==parent->lchild) //*p是双亲的左孩子
        parent->lchild=child； //*child作为*parent的左孩子
      else parent->rchild=child； //*child作为 parent的右孩子
      if(p!=q) //是情况(3)，需将*p的数据复制到*q
        q->key=p->key； //若还有其它数据域亦需复制
     } //endif
    free(p)； /释放*p占用的空间
  } //DelBSTNode
给出三种情况的不同算法
第一种：
btree * DelNode(btree *p)
{
      if (p->lchild)
      {
            btree *r = p->lchild;   //r指向其左子树;
        while(r->rchild != NULL)//搜索左子树的最右边的叶子结点r
        {
            r = r->rchild;
        }
            r->rchild = p->rchild;
            btree *q = p->lchild;   //q指向其左子树;
            free(p);
            return q;
      }
      else
      {
            btree *q = p->rchild;   //q指向其右子树;
            free(p);
            return q;
      }
}
第二种：
btree * DelNode(btree *p)
{
      if (p->lchild)
      {
            btree *r = p->lchild;   //r指向其左子树;
            btree *prer = p->lchild;   //prer指向其左子树;
        while(r->rchild != NULL)//搜索左子树的最右边的叶子结点r
        {
                  prer = r;
            r = r->rchild;
        }

        if(prer != r)//若r不是p的左孩子，把r的左孩子作为r的父亲的右孩子
        {
                  prer->rchild = r->lchild;
                  r->lchild = p->lchild; //被删结点p的左子树作为r的左子树
            }
        r->rchild = p->rchild; //被删结点p的右子树作为r的右子树

            free(p);
            return r;
      }
      else
      {
            btree *q = p->rchild;   //q指向其右子树;
            free(p);
            return q;
      }
}