1. 算法簡(jiǎn)介

二叉排序樹（Binary Sort Tree），又稱二叉查找樹（Binary Search Tree），亦稱二叉搜索樹。該樹屬于一種輸入數(shù)據(jù)就默認(rèn)產(chǎn)生一種順序的數(shù)據(jù)結(jié)構(gòu)，這不像本章前面的內(nèi)容所描述的靜態(tài)的在某一個(gè)數(shù)據(jù)段內(nèi)進(jìn)行查找，動(dòng)態(tài)查找是一種輸入時(shí)就會(huì)自動(dòng)對(duì)其進(jìn)行排序的數(shù)據(jù)結(jié)構(gòu)，前文學(xué)過的STL中的set集合其底層就是一個(gè)類似的樹形結(jié)構(gòu)紅黑樹。

2. 定義

二叉排序樹有以下性值：

a) 若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于或等于它的根結(jié)點(diǎn)的值；

b) 若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值；

c) 左、右子樹也分別為二叉排序樹；

即對(duì)于每一個(gè)根結(jié)點(diǎn)，其左孩子永遠(yuǎn)小于根，右孩子永遠(yuǎn)大于根。

3. 查找

考慮如果樹是空的，則查找結(jié)束，無匹配。如果被查找的值和根結(jié)點(diǎn)的值相等，查找成功。否則就在子樹中繼續(xù)查找。如果被查找的值小于根結(jié)點(diǎn)的值就選擇左子樹，大于根結(jié)點(diǎn)的值就選擇右子樹。

參考代碼如下：

typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */ 
 
/* 二叉樹的二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)定義 */
typedef  struct BiTNode /* 結(jié)點(diǎn)結(jié)構(gòu) */
{
    int data;   /* 結(jié)點(diǎn)數(shù)據(jù) */
    struct BiTNode *lchild, *rchild;    /* 左右孩子指針 */
} BiTNode, *BiTree;
 
/* 遞歸查找二叉排序樹T中是否存在key, */
/* 指針f指向T的雙親，其初始調(diào)用值為NULL */
/* 若查找成功，則指針p指向該數(shù)據(jù)元素結(jié)點(diǎn)，并返回TRUE */
/* 否則指針p指向查找路徑上訪問的最后一個(gè)結(jié)點(diǎn)并返回FALSE */
Status SearchBST(BiTree t, int key, BiTree f, BiTree *p) 
{  
    if (!t) /*  查找不成功 */
    { 
        *p = f;  
        return FALSE; 
    }
    else if (key == t->data) /*  查找成功 */
    { 
        *p = t;  
        return TRUE; 
    } 
    else if (key < t->data) 
        return SearchBST(t->lchild, key, t, p);  /*  在左子樹中繼續(xù)查找 */
    else  
        return SearchBST(t->rchild, key, t, p);  /*  在右子樹中繼續(xù)查找 */
}

4.插入方法及實(shí)現(xiàn)

二叉排序的插入是建立在二叉排序的查找之上的，插入一個(gè)結(jié)點(diǎn)，就是通過查找發(fā)現(xiàn)該結(jié)點(diǎn)合適插入位置，把結(jié)點(diǎn)直接放進(jìn)去。 其實(shí)在2.2節(jié)中一步步構(gòu)造二叉排序樹的過程中就是結(jié)點(diǎn)插入過程，并考慮查找的關(guān)鍵字已經(jīng)有在樹中，則指向該數(shù)據(jù)結(jié)點(diǎn)，若查找的關(guān)鍵字沒有在樹中，則指向查找路徑上最后一個(gè)結(jié)點(diǎn)。

參考代碼

struct BiTree {
    int data;
    BiTree *lchild;
    BiTree *rchild;
};
 
//在二叉排序樹中插入查找關(guān)鍵字key
BiTree* InsertBST(BiTree *t,int key)
{
    if (t == NULL)
    {
        t = new BiTree();
        t->lchild = t->rchild = NULL;
        t->data = key;
        return t;
    }
 
    if (key < t->data) 
        t->lchild = InsertBST(t->lchild, key);
    else
        t->rchild = InsertBST(t->rchild, key);
 
    return t;
}
 
//n個(gè)數(shù)據(jù)在數(shù)組d中，tree為二叉排序樹根
BiTree* CreateBiTree(BiTree *tree, int d[], int n)
{
    for (int i = 0; i < n; i++)
        tree = InsertBST(tree, d[i]);
}

5.刪除方法與實(shí)現(xiàn)

二叉樹的刪除可不再像二叉樹的插入那么容易了，以為刪除某個(gè)結(jié)點(diǎn)以后，會(huì)影響到樹的其它部分的結(jié)構(gòu)。

刪除的時(shí)候需要考慮以下幾種情況：

a)刪除結(jié)點(diǎn)為葉子結(jié)點(diǎn)；

b)刪除的結(jié)點(diǎn)只有左子樹；

c)刪除的結(jié)點(diǎn)只有右子樹

d)刪除的結(jié)點(diǎn)既有左子樹又有右子樹。

參考代碼如下：

/* 若二叉排序樹T中存在關(guān)鍵字等于key的數(shù)據(jù)元素時(shí)，則刪除該數(shù)據(jù)元素結(jié)點(diǎn), */
/* 并返回TRUE；否則返回FALSE。 */
Status DeleteBST(BiTree *T,int key)
{ 
    if(!*T) /* 不存在關(guān)鍵字等于key的數(shù)據(jù)元素 */ 
        return FALSE;
    else
    {
        if (key==(*T)->data) /* 找到關(guān)鍵字等于key的數(shù)據(jù)元素 */ 
            return Delete(T);
        else if (key<(*T)->data)
            return DeleteBST(&(*T)->lchild,key);
        else
            return DeleteBST(&(*T)->rchild,key);
 
    }
}
/* 從二叉排序樹中刪除結(jié)點(diǎn)p，并重接它的左或右子樹。 */
Status Delete(BiTree *p)
{
    BiTree q,s;
    if((*p)->rchild==NULL) /* 右子樹空則只需重接它的左子樹（待刪結(jié)點(diǎn)是葉子也走此分支) */
    {
        q=*p; *p=(*p)->lchild; free(q);
    }
    else if((*p)->lchild==NULL) /* 只需重接它的右子樹 */
    {
        q=*p; *p=(*p)->rchild; free(q);
    }
    else /* 左右子樹均不空 */
    {
        q=*p; s=(*p)->lchild;
        while(s->rchild) /* 轉(zhuǎn)左，然后向右到盡頭（找待刪結(jié)點(diǎn)的前驅(qū)） */
        {
            q=s;
            s=s->rchild;
        }
        (*p)->data=s->data; /*  s指向被刪結(jié)點(diǎn)的直接前驅(qū)（將被刪結(jié)點(diǎn)前驅(qū)的值取代被刪結(jié)點(diǎn)的值） */
        if(q!=*p)
            q->rchild=s->lchild; /*  重接q的右子樹 */ 
        else
            q->lchild=s->lchild; /*  重接q的左子樹 */
        free(s);
    }
    return TRUE;
}