在數(shù)據(jù)結(jié)構(gòu)中，線性表分為無序線性表和有序線性表.

無序線性表中的數(shù)據(jù)是無序的，因此在插入和刪除時(shí)無需遵循任何規(guī)則. 可以在數(shù)據(jù)末尾插入它，也可以在數(shù)據(jù)末尾刪除它. 但是，在搜索時(shí)需要遍歷整個(gè)數(shù)據(jù)表，這導(dǎo)致無序線性表的搜索效率低.

有序線性表的數(shù)據(jù)相反. 在搜索數(shù)據(jù)時(shí)，由于數(shù)據(jù)是有序的，因此可以通過二分法，內(nèi)插法和斐波那契搜索來實(shí)現(xiàn). 但是，在進(jìn)行插入和刪除操作時(shí)，需要保持表中數(shù)據(jù)的順序，這會(huì)花費(fèi)大量時(shí)間.

然后，我們希望找到一種具有更高插入和刪除效率以及更高搜索效率的數(shù)據(jù)結(jié)構(gòu). 因此，二進(jìn)制排序樹應(yīng)運(yùn)而生.

二進(jìn)制排序樹，也稱為二進(jìn)制搜索樹，也稱為二進(jìn)制搜索樹. 二進(jìn)制排序樹可以是空樹，也可以是具有以下屬性的二進(jìn)制樹:

（1）如果左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值都小于或等于其根節(jié)點(diǎn)的值;

（2）如果右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值都大于或等于其根節(jié)點(diǎn)的值;

（3）左和右子樹分別也是二進(jìn)制排序樹；

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

構(gòu)建過程如下:

1）索引i = 0，A [i] = 61，節(jié)點(diǎn)61作為根節(jié)點(diǎn)，如圖2.1所示:

圖2.1

2）索引i = 1，A [1] = 87，87> 61，并且節(jié)點(diǎn)61的右子元素為空，因此81是節(jié)點(diǎn)61的右子元素，如圖2.2所示:

圖2.2

3）索引i = 2，A [i] = 59，59

61，節(jié)點(diǎn)61的左子節(jié)點(diǎn)為空，因此59是節(jié)點(diǎn)61的左子節(jié)點(diǎn)，如圖2.3所示:

圖2.3

4）索引i = 3二叉排序樹 for，A [3] = 47，47

圖2.4

5）索引i = 4，A [4] = 35，35

圖2.5

使用相同的規(guī)則遍歷整個(gè)數(shù)組，以得到排序的二叉樹，如圖2.6所示.

圖2.6

由二叉樹的遞歸性質(zhì)定義，并且也可以使用以下遞歸算法搜索二叉排序樹.

如果樹為空，則搜索將不匹配而結(jié)束.

如果搜索到的值等于根節(jié)點(diǎn)的值，則搜索成功. 否則，繼續(xù)在子樹中搜索. 如果搜索到的值小于根節(jié)點(diǎn)的值，則選擇左子樹；如果搜索的值大于根節(jié)點(diǎn)的值，則選擇右子樹.

在理想情況下，每次比較后，該樹將被切成一半，幾乎是搜索的一半.

遍歷打印可以使用有序遍歷，并且打印結(jié)果是從小到大的有序數(shù)組.

查找代碼:

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ù)查找 */
}

對(duì)于圖2.6中所示的二進(jìn)制排序樹，如果搜索節(jié)點(diǎn)鍵為47，則搜索可以成功. 如果搜索節(jié)點(diǎn)鍵為75，則樹中不存在帶有鍵75的節(jié)點(diǎn)，因此搜索失敗，然后搜索指針p指向搜索路徑的最后一個(gè)節(jié)點(diǎn)，即節(jié)點(diǎn)73.

二進(jìn)制排序的插入基于對(duì)二進(jìn)制排序的搜索. 插入節(jié)點(diǎn)是通過搜索找到適當(dāng)?shù)墓?jié)點(diǎn)插入位置，然后直接將其放入. 實(shí)際上，第2.2節(jié)中逐步構(gòu)造二進(jìn)制排序樹的過程就是節(jié)點(diǎn)插入過程. 可以得出結(jié)論二叉排序樹 for，二進(jìn)制排序樹插入規(guī)則如下:

如果搜索鍵已存在于樹中，則p指向數(shù)據(jù)節(jié)點(diǎn).

如果搜索關(guān)鍵字不在樹中，則p指向搜索路徑上的最后一個(gè)節(jié)點(diǎn).

例如: 如果在圖2.6所示的二進(jìn)制排序樹中插入數(shù)據(jù)為60的節(jié)點(diǎn).

首先找到數(shù)據(jù)為60的節(jié)點(diǎn). 在二進(jìn)制排序樹中沒有數(shù)據(jù)為60的節(jié)點(diǎn)，因此搜索失敗. 此時(shí)，搜索指針p指向搜索路徑的最后一個(gè)節(jié)點(diǎn)，即點(diǎn)59. 由于60> 59并且59節(jié)點(diǎn)的右子樹為空，因此60節(jié)點(diǎn)被視為該節(jié)點(diǎn)的右子節(jié)點(diǎn). 59個(gè)節(jié)點(diǎn)，并且插入完成. 插入的二進(jìn)制排序樹如圖2.8所示.

圖2.8

插入代碼:

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

刪除二叉樹不再像插入二叉樹那樣容易，因?yàn)檎J(rèn)為刪除節(jié)點(diǎn)會(huì)影響樹的其他部分的結(jié)構(gòu).

刪除時(shí)需要考慮以下情況:

1）將該節(jié)點(diǎn)刪除為葉節(jié)點(diǎn)；

2）刪除的節(jié)點(diǎn)只是左子樹；

3）刪除的節(jié)點(diǎn)只是正確的子樹

4）刪除的節(jié)點(diǎn)同時(shí)具有左子樹和右子樹.

考慮到前三種情況，處理方法相對(duì)簡(jiǎn)單.

例如: 如果要?jiǎng)h除圖2.8中的節(jié)點(diǎn)93，只需直接刪除該節(jié)點(diǎn). 刪除后的二進(jìn)制排序樹如圖2.9所示:

圖2.9

如果要?jiǎng)h除的節(jié)點(diǎn)是僅具有右側(cè)子樹的節(jié)點(diǎn)35，則只需刪除節(jié)點(diǎn)35并將節(jié)點(diǎn)35替換為右側(cè)子樹37節(jié)點(diǎn). 刪除的二進(jìn)制排序樹如圖2.10所示:

圖2.10

僅刪除左側(cè)子樹的節(jié)點(diǎn)與此情況類似.

情況4相對(duì)復(fù)雜. 對(duì)于要?jiǎng)h除的節(jié)點(diǎn)同時(shí)具有左子樹和右子樹的情況，最好的方法是找到其余序列中最接近的節(jié)點(diǎn)以替換已刪除的節(jié)點(diǎn). 這種替換不會(huì)影響樹的整體結(jié)構(gòu). 那么如何獲得最近的節(jié)點(diǎn)呢？

按順序遍歷可用于獲取已刪除節(jié)點(diǎn)的前任和后繼. 選擇前任節(jié)點(diǎn)或后繼節(jié)點(diǎn)，而不要?jiǎng)h除該節(jié)點(diǎn).

例如: 要?jiǎng)h除的節(jié)點(diǎn)為47，圖2.8中二進(jìn)制排序樹的有序遍歷順序?yàn)?5 37 47 51 59 60 61 73 87 9398. 則節(jié)點(diǎn)47的前任節(jié)點(diǎn)為37節(jié)點(diǎn)，而37節(jié)點(diǎn)可以直接替換47節(jié)點(diǎn). 替換后的二進(jìn)制排序樹如圖2.11所示:

圖2.11

刪除代碼:

/* 若二叉排序樹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;
}

二進(jìn)制排序樹是一種具有更高搜索和插入效率的數(shù)據(jù)結(jié)構(gòu). 同時(shí)，二叉樹也是二叉樹學(xué)習(xí)的重點(diǎn)和難點(diǎn). 我希望通過本文的學(xué)習(xí)，我可以掌握搜索，插入和刪除二進(jìn)制排序樹的基本操作. 我也希望讀者能給予指導(dǎo).

本文來自本站，轉(zhuǎn)載請(qǐng)注明本文網(wǎng)址：
http://www.pc-fly.com/a/jisuanjixue/article-286323-1.html