二叉排序樹(shù)的定義
　　二叉排序樹(shù)(Binary Sort Tree)又稱(chēng)二叉查找(搜索)樹(shù)(Binary Search Tree)。其定義為：二叉排序樹(shù)或者是空樹(shù)，或者是滿足如下性質(zhì)的二叉樹(shù)：
①若它的左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；
②若它的右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；
③左、右子樹(shù)本身又各是一棵二叉排序樹(shù)。
　　上述性質(zhì)簡(jiǎn)稱(chēng)二叉排序樹(shù)性質(zhì)(BST性質(zhì))，故二叉排序樹(shù)實(shí)際上是滿足BST性質(zhì)的二叉樹(shù)。

 

class BST{
    private:
        typedef struct Node{
               int key;
               Node *pLeft,*pRight;
        }Node;
        Node *pA,*pB,*pRoot;
    public:
        BST(){pRoot=NULL;}
        ~BST(){ DestroyTree(pRoot);}
        void DestroyTree(Node *p);
        void Input();
        void Insert(int v);
        int  MaxKey();
        int  MinKey();
};

void BST::DestroyTree(Node *p){
    if(p)
    {
        return DestroyTree(p->pLeft);
        return DestroyTree(p->pRight);
        delete p;
    }
}

void BST::Input(){
    int n,i,iTemp;
    cin>>n;
    for(i=1;i<=n;++i)
    {
        cin>>iTemp;
        Insert(iTemp);
    }
}

void BST::Insert(int v){
    pA=pRoot;
    while(pA)
    {
        if(pA->key==v) return;
        pB=pA;
        pA=(v<pA->key)?pA->pLeft:pA->pRight;
    }
    pA=new Node;
    pA->key=v;
    pA->pLeft=pA->pRight=NULL;
    if(pRoot==NULL)
        pRoot=pA;
    else if(v<pB->key)
         pB->pLeft=pA;
         else
         pB->pRight=pA;
}

int BST::MaxKey(){
    pA=pRoot;
    while(pA->pRight)
        pA=pA->pRight;
    return pA->key;
}

int BST::MinKey(){
    pA=pRoot;
    while(pA->pLeft)
        pA=pA->pLeft;
    return pA->key;
}

2叉排序樹(shù)最復(fù)雜的是刪除：
        對(duì)于一般的二叉樹(shù)來(lái)說(shuō)，刪去樹(shù)中的一個(gè)結(jié)點(diǎn)是沒(méi)有意義的，因?yàn)樗鼘⑹挂员粍h除的結(jié)點(diǎn)為根的子樹(shù)變成森林，破壞了整棵樹(shù)的結(jié)構(gòu)
但是，對(duì)于二叉排序樹(shù)，刪去樹(shù)上的一個(gè)結(jié)點(diǎn)相當(dāng)于刪去有序序列中的一個(gè)記錄，只要在刪除某個(gè)結(jié)點(diǎn)后不改變二叉排序樹(shù)的特性即可。
      在二叉排序樹(shù)上刪除一個(gè)結(jié)點(diǎn)的算法如下：
btree * DeleteBST(btree *b, ElemType x)
{
      if (b)
      {
            if (b->data == x)
                  b = DelNode(b);
            else if (b->data > x)
                  b->lchild = DeleteBST(b->lchild, x);
            else
                  b->rchild = DeleteBST(b->rchild, x);
      }
      return b;
}


其中刪除過(guò)程有兩種方法。
第一種過(guò)程如下：
1。若p有左子樹(shù)，找到其左子樹(shù)的最右邊的葉子結(jié)點(diǎn)r，用該葉子結(jié)點(diǎn)r來(lái)替代p，把r的左孩子
作為r的父親的右孩子。
2。若p沒(méi)有左子樹(shù)，直接用p的右孩子取代它。

第二種過(guò)程如下：
1。若p有左子樹(shù)，用p的左孩子取代它；找到其左子樹(shù)的最右邊的葉子結(jié)點(diǎn)r，把p的右子樹(shù)作為r
的右子樹(shù)。
2。若p沒(méi)有左子樹(shù)，直接用p的右孩子取代它。
    兩種方法各有優(yōu)劣，第一種操作簡(jiǎn)單一點(diǎn)點(diǎn)，但均衡性不如第二種，因?yàn)樗鼘⒔Y(jié)點(diǎn)p的右子樹(shù)
全部移到左邊來(lái)了。下面將分別以?xún)煞N種思路編寫(xiě)代碼。
第一種：
btree * DelNode(btree *p)
{
      if (p->lchild)
      {
            btree *r = p->lchild;   //r指向其左子樹(shù);
        while(r->rchild != NULL)//搜索左子樹(shù)的最右邊的葉子結(jié)點(diǎn)r
        {
            r = r->rchild;
        }
            r->rchild = p->rchild;

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

第二種：
btree * DelNode(btree *p)
{
      if (p->lchild)
      {
            btree *r = p->lchild;   //r指向其左子樹(shù);
            btree *prer = p->lchild;   //prer指向其左子樹(shù);
        while(r->rchild != NULL)//搜索左子樹(shù)的最右邊的葉子結(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的左子樹(shù)作為r的左子樹(shù)
            }
        r->rchild = p->rchild; //被刪結(jié)點(diǎn)p的右子樹(shù)作為r的右子樹(shù)

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

但是上面這種方法，把r移來(lái)移去，很容易出錯(cuò)，其實(shí)在這里我們刪除的只是p的元素值，而不是它的地址，所以完全沒(méi)有必要移動(dòng)指針。仔細(xì)觀察，發(fā)現(xiàn)我們刪除的地址實(shí)際上是p的左子樹(shù)的最右邊的葉子結(jié)點(diǎn)r的地址，所以我們只要把r的數(shù)據(jù)填到p中，然后把r刪除即可。
算法如下：

btree * DelNode(btree *p)
{
      if (p->lchild)
      {
            btree *r = p->lchild;   //r指向其左子樹(shù);
            btree *prer = p->lchild;   //prer指向其左子樹(shù);
        while(r->rchild != NULL)//搜索左子樹(shù)的最右邊的葉子結(jié)點(diǎn)r
        {
                  prer = r;
            r = r->rchild;
        }
            p->data = r->data;

        if(prer != r)//若r不是p的左孩子，把r的左孩子作為r的父親的右孩子
                  prer->rchild = r->lchild;
            else
            p->lchild = r->lchild; //否則結(jié)點(diǎn)p的左子樹(shù)指向r的左子樹(shù)

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

                                                                                                                   刪除的部分是轉(zhuǎn)載,作者寫(xiě)的比較清楚,碼的思路比較清晰....!