二排筋

1.二叉排序樹的概念:

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

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

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

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

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

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

2.二叉排序樹的插入:

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

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

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

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

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

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

3. 二叉排序樹生成：

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

說(shuō)明：

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

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

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

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

5. 二叉排序樹的刪除:

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

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

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

⑶ 若結(jié)點(diǎn)*p的左、右子樹均非空，先找到*p的中序前趨結(jié)點(diǎn)*s（注意*s是*p的左子樹中的最右下的結(jié)點(diǎn)，它的右鏈域?yàn)榭眨缓笥袃煞N做法：

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

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

6. 刪除算法演示 :

7. 二叉排序樹的查找:

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

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

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

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

最壞情況示例

就平均性能而言，

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