1、二叉搜索樹是二叉樹的一種，樹的每個結(jié)點(diǎn)含有一個數(shù)據(jù)項，每個數(shù)據(jù)項有一個鍵值。結(jié)點(diǎn)的存儲位置是由鍵值的大小決定的，所以二叉搜索樹是關(guān)聯(lián)式容器。
(1)、 若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的鍵值均小于它的根結(jié)點(diǎn)的鍵值；
(2)、若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的鍵值均大于它的根結(jié)點(diǎn)的鍵值；
(3)、它的左、右子樹也分別為二叉排序樹。
注意：：：二叉排序樹是一種動態(tài)樹表，樹的結(jié)構(gòu)通常不是一次生成的。而是在查找的過程中，當(dāng)樹中不存在關(guān)鍵字等于給定值的節(jié)點(diǎn)時再進(jìn)行插入。新插入的結(jié)點(diǎn)一定是一個新添加的葉子結(jié)點(diǎn)，并且是查找不成功時查找路徑上訪問的最后一個結(jié)點(diǎn)的左孩子或右孩子結(jié)點(diǎn)。

2、插入與查找算法：
查找：
（1）、若二叉排序樹非空，將給定值與根節(jié)點(diǎn)的關(guān)鍵字值比較，若相等，則查找成功；
（2）、若不等，則當(dāng)根節(jié)點(diǎn)的關(guān)鍵字值大于給定值時，到根的左子樹中進(jìn)行查找；
（3）、否則到根的右子樹中進(jìn)行查找。若找到，則查找過程是走了一條從樹根到所找到節(jié)點(diǎn)的路徑；
（4）、否則，查找過程終止于一棵空樹。
//① 、普通查找，查找不成功返回NULL
遞歸思想：
 BiTree SearchBST (BiTree *T，KeyType key)
{
    //在根指針T所指二叉排序樹中遞歸地查找某關(guān)鍵字等于key的數(shù)據(jù)元素
    //若查找成功，則返回指向該數(shù)據(jù)元素結(jié)點(diǎn)的指針，否則返回空指針
        if( (!T)||(key==T—>data.key))
            return (T)； //查找結(jié)束,此時T為NULL，或者為該結(jié)點(diǎn)
        else if (key< T—>data.key)
                return(SearchBST(T—>lchild，key))； //在左子樹中繼續(xù)查找
                else
                return(SearchBST(T —>rchild，key))；// 在右子樹中繼續(xù)查找
    }//SearchBST

非遞歸思想：
BiTree SearchBST (BiTree *root，KeyType key)
{ 
   BiTree *p；
   if( root ＝＝ NULL)return NULL；//查找結(jié)束,此時根為NULL，
   p ＝ root；
   while(p!=NULL)
   { 
        if(p －>key==Key)breat；
       if( Key < p ->key) p ＝p －>lchild；//在左子樹中繼續(xù)查找
         else p ＝ p －>rchild；//在右子樹中繼續(xù)查找
    }
   return p；
}
//② 、查找不成功，返回插入位置
    //在根指針T所指二叉排序樹中遞歸地查找其關(guān)鍵字等于key的數(shù)據(jù)元素，
    //若查找成功，則指針p指向該數(shù)據(jù)元素結(jié)點(diǎn)，并返回TRUE，
    //否則指針p指向查找路徑上訪問的最后一個結(jié)點(diǎn)并返回FALSE，
    //指針f指向T的雙親，其初始調(diào)用值為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)； //在左子樹中繼續(xù)查找
                        else SearchBST(T—>rchild，key，T，p)；//在右子樹中繼續(xù)查找
    }//SearchBST

插入：
（1）、首先執(zhí)行查找算法，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)。沒找到則新建子結(jié)點(diǎn)

（2）、判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子。將被插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。

（3）、若二叉樹為空。則首先單獨(dú)生成根結(jié)點(diǎn)

基于BOOL SearchBST(BiTree *T，KeyType key，BiTree *f，BiTree &p)的插入算法
相當(dāng)于新建子樹。
 //當(dāng)二叉排序樹T中不存在關(guān)鍵字等于e.key的數(shù)據(jù)元素時,插入e并返回TRUE，否則返回FALSE
Status Insert BST(BiTree &T，ElemType e)
{
            if(!SearchBST(T，e.key，NULL，p) ) //返回P為插入的結(jié)點(diǎn)點(diǎn)
        { //先查找，不成功新建結(jié)點(diǎn)
            s=(BiTree)malloc(sizeof(BiTNode))；
            s->data=e； s->lchild= s->rchild=NULL；
            if (!p) T = s； //被插結(jié)點(diǎn)*s為新的根結(jié)點(diǎn) ，原樹為空
            else if (e.key<p->data.key) p->lchild=s； //被插結(jié)點(diǎn)*s為左孩子
                    else p—>rchild=s //被插結(jié)點(diǎn)*s為右孩子
            return TRUE；
          }
        else 
      return FALSE; //樹中已有關(guān)鍵字相同的結(jié)點(diǎn)，不再插入
    }// Insert BST

  void InsertBST(BSTree *Tptr，KeyType key)
      {
//若二叉排序樹 *Tptr中沒有關(guān)鍵字為key，則插入，否則直接返回
        BSTNode *f，*p=*TPtr； //p的初值指向根結(jié)點(diǎn)
        while(p){ //查找插入位置
          if(p->key==key) return；//樹中已有key，無須插入
          f=p； //f保存當(dāng)前查找的結(jié)點(diǎn)
          p=(key<p->key)?p->lchild：p->rchild；
            //若key<p->key，則在左子樹中查找，否則在右子樹中查找
         } //endwhile
         //f為插入的結(jié)點(diǎn)
        p=(BSTNode *)malloc(sizeof(BSTNode))；
        p->key=key； p->lchild=p->rchild=NULL； //生成新結(jié)點(diǎn)
        if(*TPtr==NULL) //原樹為空
           *Tptr=p； //新插入的結(jié)點(diǎn)為新的根
        else //原樹非空時將新結(jié)點(diǎn)關(guān)p作為關(guān)f的左孩子或右孩子插入
          if(key<f->key)
            f->lchild=p；
          else f->rchild=p；
       } //InsertBST

4、刪除算法
①刪除操作的一般步驟
(1) 進(jìn)行查找
    　查找時，令p指向當(dāng)前訪問到的結(jié)點(diǎn)，parent指向其雙親(其初值為NULL)。若樹中找不到被刪結(jié)點(diǎn)則返回，否則被刪結(jié)點(diǎn)是*p。
(2) 刪去*p。
    　刪*p時，應(yīng)將*p的子樹(若有)仍連接在樹上且保持BST性質(zhì)不變。按*p的孩子數(shù)目分三種情況進(jìn)行處理。

②刪除*p結(jié)點(diǎn)的三種情況
(1)*p是葉子(即它的孩子數(shù)為0)
    　無須連接*p的子樹，只需將*p的雙親*parent中指向*p的指針域置空即可。

(2)*p只有一個孩子*child
    　只需將*child和*p的雙親直接連接后，即可刪去*p。
  注意：
    　*p既可能是*parent的左孩子也可能是其右孩子，而*child可能是*p的左孩子或右孩子，故共有4種狀態(tài)。
(3)*p有兩個孩子
    　先令q=p，將被刪結(jié)點(diǎn)的地址保存在q中；然后找*q的中序后繼*p，并在查找過程中仍用parent記住*p的雙親位置。*q的中序后繼*p一定是*q的右子樹中最左下的結(jié)點(diǎn)，它無左子樹。因此，可以將刪去*q的操作轉(zhuǎn)換為刪去的*p的操作，即在釋放結(jié)點(diǎn)*p之前將其數(shù)據(jù)復(fù)制到*q中，就相當(dāng)于刪去了*q。
③二叉排序樹刪除算法
分析：
    　上述三種情況都能統(tǒng)一到情況(2)，算法中只需針對情況(2)處理即可。
    　注意邊界條件：若parent為空，被刪結(jié)點(diǎn)*p是根，故刪去*p后，應(yīng)將child置為根。


算法：刪除關(guān)鍵字為key的結(jié)點(diǎn)
void DelBSTNode(BSTree *Tptr，KeyType key)
 {
//在二叉排序樹*Tptr中刪去關(guān)鍵字為key的結(jié)點(diǎn)
  BSTNode *parent=NUll，*p=*Tptr，*q，*child；
  while(p)
{ 
     //從根開始查找關(guān)鍵字為key的待刪結(jié)點(diǎn)
    if(p->key==key) break；//已找到，跳出查找循環(huán)
    parent=p； //parent指向*p的雙親
    p=(key<p->key)?p->lchild：p->rchild； //在關(guān)p的左或右子樹中繼續(xù)找
 } 
//注意：也可以使用基于BOOL SearchBST(BiTree *T，KeyType key，BiTree *f，BiTree &p)的查找算法
//結(jié)果是  parent 記錄了要刪除結(jié)點(diǎn)的父結(jié)點(diǎn)，p指向要刪除的結(jié)點(diǎn)

      if(!p) return； //找不到被刪結(jié)點(diǎn)則返回
     q=p； //q記住被刪結(jié)點(diǎn)*p
     if(q->lchild && q->rchild) //*q的兩個孩子均非空，故找*q的中序后繼*p
    for(parent=q，p=q->rchild； p->lchild； parent=p，p=p=->lchild)；
  //現(xiàn)在情況(3)已被轉(zhuǎn)換為情況(2)，而情況(1)相當(dāng)于是情況(2)中child=NULL的狀況
    child=(p->lchild)?p->lchild：p->rchild；//若是情況(2)，則child非空；否則child為空
    if(!parent) //*p的雙親為空，說明*p為根，刪*p后應(yīng)修改根指針
      *Tptr=child； //若是情況(1)，則刪去*p后，樹為空；否則child變?yōu)楦?br />    else{ //*p不是根，將*p的孩子和*p的雙親進(jìn)行連接，*p從樹上被摘下
      if(p==parent->lchild) //*p是雙親的左孩子
        parent->lchild=child； //*child作為*parent的左孩子
      else parent->rchild=child； //*child作為 parent的右孩子
      if(p!=q) //是情況(3)，需將*p的數(shù)據(jù)復(fù)制到*q
        q->key=p->key； //若還有其它數(shù)據(jù)域亦需復(fù)制
     } //endif
    free(p)； /釋放*p占用的空間
  } //DelBSTNode
給出三種情況的不同算法
第一種：
btree * DelNode(btree *p)
{
      if (p->lchild)
      {
            btree *r = p->lchild;   //r指向其左子樹;
        while(r->rchild != NULL)//搜索左子樹的最右邊的葉子結(jié)點(diǎn)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)//搜索左子樹的最右邊的葉子結(jié)點(diǎn)r
        {
                  prer = r;
            r = r->rchild;
        }

        if(prer != r)//若r不是p的左孩子，把r的左孩子作為r的父親的右孩子
        {
                  prer->rchild = r->lchild;
                  r->lchild = p->lchild; //被刪結(jié)點(diǎn)p的左子樹作為r的左子樹
            }
        r->rchild = p->rchild; //被刪結(jié)點(diǎn)p的右子樹作為r的右子樹

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