1 前言

數(shù)據(jù)結構中，線性表分為無序線性表和有序線性表。
無序線性表的數(shù)據(jù)是雜亂無序的，所以在插入和刪除時，沒有什么必須遵守的規(guī)則，可以插入在數(shù)據(jù)尾部或者刪除在數(shù)據(jù)尾部。但是在查找的時候，需要遍歷整個數(shù)據(jù)表，導致無序線性表的查找效率低。
有序線性表的數(shù)據(jù)則相反，查找數(shù)據(jù)時的時候因為數(shù)據(jù)是有序的，可以用二分法、插值法、斐波那契查找法來實現(xiàn)。但是，當進行插入和刪除操作時，需要維護表中數(shù)據(jù)的有序性，會耗費大量的時間。
那么，我們希望找到一種數(shù)據(jù)結構，既可以有較高的插入和刪除效率，并且具備較高的查找效率，因此，二叉排序樹應運而生。

2 二叉排序樹

2.1 定義

二叉排序樹（Binary Sort Tree），又稱二叉查找樹（Binary Search Tree），也稱二叉搜索樹。二叉排序樹或者是一棵空樹，或者是具有下列性質的二叉樹：

（1）若左子樹不空，則左子樹上所有結點的值均小于或等于它的根結點的值；
（2）若右子樹不空，則右子樹上所有結點的值均大于或等于它的根結點的值；
（3）左、右子樹也分別為二叉排序樹；

2.2 構造一棵二叉排序樹

現(xiàn)有序列：61 87 59 47 35 73 51 98 37 93

構造過程如下：
1）索引 i = 0，A[i] = 61，結點61作為根結點，如圖2.1：

圖2.1

2）索引 i = 1，A[1] = 87, 87 > 61，且結點61右孩子為空，故81為61結點的右孩子，如圖2.2：

圖2.2

3）索引 i = 2，A[i] = 59，59 <
61，且結點61左孩子為空，故59為61結點的左孩子，如圖2.3：

圖2.3

4）索引 i = 3，A[3] = 47，47 < 59，且結點59左孩子為空，故47為59結點的左孩子，如圖2.4：

圖2.4

5）索引 i = 4，A[4] = 35，35 < 47，且結點47左孩子為空，故35為47結點的左孩子，如圖2.5：

圖2.5

采用同樣規(guī)則遍歷整個數(shù)組得到如圖2.6所示的一棵排序二叉樹。

圖2.6

2.3 二叉排序樹查找

由二叉樹的遞歸定義性質，二叉排序樹的查找同樣可以使用如下遞歸算法查找。

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

在理想情況下，每次比較過后，樹會被砍掉一半，近乎折半查找。
遍歷打印可以使用中序遍歷，打印出來的結果是從小到大的有序數(shù)組。
查找代碼：

typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結果狀態(tài)代碼，如OK等 */ 

/* 二叉樹的二叉鏈表結點結構定義 */
typedef  struct BiTNode /* 結點結構 */
{
    int data;   /* 結點數(shù)據(jù) */
    struct BiTNode *lchild, *rchild;    /* 左右孩子指針 */
} BiTNode, *BiTree;


/* 遞歸查找二叉排序樹T中是否存在key, */
/* 指針f指向T的雙親，其初始調用值為NULL */
/* 若查找成功，則指針p指向該數(shù)據(jù)元素結點，并返回TRUE */
/* 否則指針p指向查找路徑上訪問的最后一個結點并返回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ù)查找 */
}

對于圖2.6所示的二叉排序樹，若查找結點key為47則可以查找成功，若查找結點key為75，樹中不存在key為75的結點，故查找失敗，則查找指針p指向查找路徑的最后一個結點，即結點73。

2.4 二叉排序樹插入

二叉排序的插入是建立在二叉排序的查找之上的，插入一個結點，就是通過查找發(fā)現(xiàn)該結點合適插入位置，把結點直接放進去。 其實在2.2節(jié)中一步步構造二叉排序樹的過程中就是結點插入過程。由此可以得出二叉排序樹插入規(guī)則如下：

若查找的key已經(jīng)有在樹中，則p指向該數(shù)據(jù)結點。
若查找的key沒有在樹中，則p指向查找路徑上最后一個結點。

例如：若在圖2.6展示的二叉排序樹中插入結點數(shù)據(jù)為60的結點。
首先查找結點數(shù)據(jù)為60的結點，二叉排序樹中不存在結點為60的結點，因此查找失敗。此時查找指針p指向查找路徑最后一個結點即指向59結點。由于60>59且59結點右子樹為空，故將60結點作為59結點的右孩子，插入完成。插入后的二叉排序樹如圖2.8所示。

圖2.8

插入代碼：

struct BiTree {
    int data;
    BiTree *lchild;
    BiTree *rchild;
};
 
//在二叉排序樹中插入查找關鍵字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個數(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]);
}

2.5 二叉排序樹刪除

二叉樹的刪除可不再像二叉樹的插入那么容易了，以為刪除某個結點以后，會影響到樹的其它部分的結構。
刪除的時候需要考慮以下幾種情況：

1）刪除結點為葉子結點；
2）刪除的結點只有左子樹；
3）刪除的結點只有右子樹
4）刪除的結點既有左子樹又有右子樹。

考慮前三種情況，處理方式比較簡單。
例如：若要刪除圖2.8中的結點93，則直接刪除該結點即可。刪除后二叉排序樹如圖2.9所示：

圖2.9

若要刪除的結點為結點35，結點35只有右子樹，只需刪除結點35，將右子樹37結點替代結點35即可。刪除后的二叉排序樹如圖2.10所示：

圖2.10

刪除只有左子樹的結點與此情況類似。

情況4相對比較復雜，對于待刪除結點既有左子樹又有右子樹的情形，最佳辦法是在剩余的序列中找到最為接近的結點來代替刪除結點。這種代替并不會影響到樹的整體結構。那么最為接近的結點如何獲取呢？
可以采用中序遍歷的方式來得到刪除結點的前驅和后繼結點。選取前驅結點或者后繼結點代替刪除結點即可。
例如：待刪除的結點為47，圖2.8中二叉排序樹的中序遍歷序列為35 37 47 51 59 60 61 73 87 93 98。則結點47的前驅結點為37，則直接將37結點替代47結點即可。替換后的二叉排序樹如圖2.11所示：

圖2.11

刪除代碼：

/* 若二叉排序樹T中存在關鍵字等于key的數(shù)據(jù)元素時，則刪除該數(shù)據(jù)元素結點, */
/* 并返回TRUE；否則返回FALSE。 */
Status DeleteBST(BiTree *T,int key)
{ 
    if(!*T) /* 不存在關鍵字等于key的數(shù)據(jù)元素 */ 
        return FALSE;
    else
    {
        if (key==(*T)->data) /* 找到關鍵字等于key的數(shù)據(jù)元素 */ 
            return Delete(T);
        else if (key<(*T)->data)
            return DeleteBST(&(*T)->lchild,key);
        else
            return DeleteBST(&(*T)->rchild,key);

    }
}
/* 從二叉排序樹中刪除結點p，并重接它的左或右子樹。 */
Status Delete(BiTree *p)
{
    BiTree q,s;
    if((*p)->rchild==NULL) /* 右子樹空則只需重接它的左子樹（待刪結點是葉子也走此分支) */
    {
        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) /* 轉左，然后向右到盡頭（找待刪結點的前驅） */
        {
            q=s;
            s=s->rchild;
        }
        (*p)->data=s->data; /*  s指向被刪結點的直接前驅（將被刪結點前驅的值取代被刪結點的值） */
        if(q!=*p)
            q->rchild=s->lchild; /*  重接q的右子樹 */ 
        else
            q->lchild=s->lchild; /*  重接q的左子樹 */
        free(s);
    }
    return TRUE;
}

3 結語

二叉排序樹是一種查找與插入效率均較為高效的數(shù)據(jù)結構，同時，二叉排序樹也是二叉樹學習中的重點與難點。希望通過本篇的學習能夠掌握二叉排序樹的查找、插入與刪除等基本操作，也希望讀者給出指導意見。