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;
      }
}