二叉排序樹查找

標籤: 暫無標籤

9

更新時間: 2013-09-04

廣告

二叉排序樹查找的插入和刪除結點十分方便。

廣告

1 二叉排序樹查找 -主題

 二叉排序樹查找

2 二叉排序樹查找 -內容

1.二叉排序樹的概念:
  二叉排序樹是一種動態樹表。
   二叉排序樹的定義:二叉排序樹或者是一棵空樹,
   或者是一棵具有如下性質的二叉樹:
     ⑴ 若它的左子樹非空,則左子樹上所有結點的值均小於根結點的值;
     ⑵ 若它的右子樹非空,則右子樹上所有結點的值均大於根結點的值;
     ⑶ 左、右子樹本身又各是一棵二叉排序樹。二叉排序樹的性質: 按中序遍歷二叉排序樹,所得到的中序遍歷序列是一個遞增有序序列。

2.二叉排序樹的插入:
   在二叉排序樹中插入新結點,要保證插入后的二叉樹仍符合二叉排序樹的定義。
   插入過程:若二叉排序樹為空,則待插入結點*S作為根結點插入到空樹中;
   當非空時,將待插結點關鍵字S->key和樹根關鍵字t->key進行比較,
   若s->key = t->key,則無須插入,若s->key< t->key,則插入到根的左子樹中,
   若s->key> t->key,則插入到根的右子樹中。而子樹中的插入過程和在樹中的插入過程相同,
   如此進行下去,直到把結點*s作為一個新的樹葉插入到二叉排序樹中,或者直到發現樹已有相同關鍵字的結點為止。

3. 二叉排序樹生成:
   從空的二叉排序樹開始,經過一系列的查找插入操作以後,生成了一棵二叉排序樹。
   說明:
     ① 每次插入的新結點都是二叉排序樹上新的葉子結點。
     ② 由不同順序的關鍵字序列,會得到不同二叉排序樹。
     ③ 對於一個任意的關鍵字序列構造一棵二叉排序樹,其實質上對關鍵字進行排序。

4.二叉排序樹查找的程序實現:

5. 二叉排序樹的刪除:
  
假設被刪結點是*p,其雙親是*f,不失一般性,設*p是*f的左孩子,下面分三種情況討論:
⑴ 若結點*p是葉子結點,則只需修改其雙親結點*f的指針即可。
⑵ 若結點*p只有左子樹PL或者只有右子樹PR,則只要使PL或PR 成為其雙親結點的左子樹即可。
⑶ 若結點*p的左、右子樹均非空,先找到*p的中序前趨結點*s(注意*s是*p的左子樹中的最右下的結點,它的右鏈域為空),然後有兩種做法:
① 令*p的左子樹直接鏈到*p的雙親結點*f的左鏈上,而*p的右子樹鏈到*p的中序前趨結點*s的右鏈上。
② 以*p的中序前趨結點*s代替*p(即把*s的數據複製到*p中),將*s的左子樹鏈到*s的雙親結點*q的左(或右)鏈上。


6. 刪除演算法演示 :

7. 二叉排序樹的查找:
  在二叉排序樹中進行查找的過程和二分查找類似,也是一個逐步縮小查找範圍的過程。若查找成功,則是走了一條從根結點到待查結點的路徑;若查找失敗,則是走了一條根結點到某個葉子結點的路徑。因此,查找過程中和關鍵字比較的次數不超過樹的深度。
   由於含有n個結點的二叉排序樹不唯一,形態和深度可能不同。故含有n個結點的二叉排序樹的平均查找長度和樹的形態有關。
   最好的情況是: 二叉排序樹和二叉判定樹形態相同。
   最壞的情況是: 二叉排序樹為單支樹,這時的平均查找長度和順序查找時相同。
   最壞情況示例 
   

3 二叉排序樹查找 -就平均性能而言,

 

二叉排序樹上的查找和二分查找相差不大,並且二叉排序樹上的插入和刪除結點十分方便,無須大量移動結點。  

廣告