二叉排序數(shù)概述

1.二叉排序樹的概念:

二叉排序樹是一種動態(tài)樹表。

二叉排序樹的定義：二叉排序樹或者是一棵空樹，

或者是一棵具有如下性質(zhì)的二叉樹：

⑴ 若它的左子樹非空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值；

⑵ 若它的右子樹非空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值；

⑶ 左、右子樹本身又各是一棵二叉排序樹。二叉排序樹的性質(zhì)： 按中序遍歷二叉排序樹，所得到的中序遍歷序列是一個遞增有序序列。

2.二叉排序樹的插入:

在二叉排序樹中插入新結(jié)點，要保證插入后的二叉樹仍符合二叉排序樹的定義。

插入過程：若二叉排序樹為空，則待插入結(jié)點*S作為根結(jié)點插入到空樹中；

當(dāng)非空時，將待插結(jié)點關(guān)鍵字S->key和樹根關(guān)鍵字t->key進(jìn)行比較，

若s->key = t->key,則無須插入，若s->key< t->key,則插入到根的左子樹中，

若s->key> t->key,則插入到根的右子樹中。而子樹中的插入過程和在樹中的插入過程相同，

如此進(jìn)行下去，直到把結(jié)點*s作為一個新的樹葉插入到二叉排序樹中，或者直到發(fā)現(xiàn)樹已有相同關(guān)鍵字的結(jié)點為止。

3. 二叉排序樹生成：

從空的二叉排序樹開始，經(jīng)過一系列的查找插入操作以后，生成了一棵二叉排序樹。

說明：

① 每次插入的新結(jié)點都是二叉排序樹上新的葉子結(jié)點。

② 由不同順序的關(guān)鍵字序列，會得到不同二叉排序樹。

③ 對于一個任意的關(guān)鍵字序列構(gòu)造一棵二叉排序樹，其實質(zhì)上對關(guān)鍵字進(jìn)行排序。

4.二叉排序樹查找的程序?qū)崿F(xiàn):

5. 二叉排序樹的刪除:

假設(shè)被刪結(jié)點是*p，其雙親是*f，不失一般性，設(shè)*p是*f的左孩子，下面分三種情況討論：

⑴ 若結(jié)點*p是葉子結(jié)點，則只需修改其雙親結(jié)點*f的指針即可。

⑵ 若結(jié)點*p只有左子樹PL或者只有右子樹PR，則只要使PL或PR 成為其雙親結(jié)點的左子樹即可。

⑶ 若結(jié)點*p的左、右子樹均非空，先找到*p的中序前趨結(jié)點*s（注意*s是*p的左子樹中的最右下的結(jié)點，它的右鏈域為空），然后有兩種做法：

① 令*p的左子樹直接鏈到*p的雙親結(jié)點*f的左鏈上,而*p的右子樹鏈到*p的中序前趨結(jié)點*s的右鏈上。

② 以*p的中序前趨結(jié)點*s代替*p（即把*s的數(shù)據(jù)復(fù)制到*p中），將*s的左子樹鏈到*s的雙親結(jié)點*q的左（或右）鏈上。

6. 刪除算法演示 :

7. 二叉排序樹的查找:

在二叉排序樹中進(jìn)行查找的過程和二分查找類似，也是一個逐步縮小查找范圍的過程。若查找成功，則是走了一條從根結(jié)點到待查結(jié)點的路徑；若查找失敗，則是走了一條根結(jié)點到某個葉子結(jié)點的路徑。因此，查找過程中和關(guān)鍵字比較的次數(shù)不超過樹的深度。

由于含有n個結(jié)點的二叉排序樹不唯一，形態(tài)和深度可能不同。故含有n個結(jié)點的二叉排序樹的平均查找長度和樹的形態(tài)有關(guān)。

最好的情況是： 二叉排序樹和二叉判定樹形態(tài)相同。

最壞的情況是： 二叉排序樹為單支樹，這時的平均查找長度和順序查找時相同。

最壞情況示例

就平均性能而言，

二叉排序樹上的查找和二分查找相差不大，并且二叉排序樹上的插入和刪除結(jié)點十分方便，無須大量移動結(jié)點。

二叉排序樹查找