二叉排序樹(Binary Search Tree)是一種動態樹表。 二叉排序樹的定義：二叉排序樹或者是一棵空樹， 或者是一棵具有如下性質的二叉樹： ⑴ 若它的左子樹非空，則左子樹上所有結點的值均小於根結點的值； ⑵ 若它的右子樹非空，則右子樹上所有結點的值均大於根結點的值； ⑶ 左、右子樹本身又各是一棵二叉排序樹。二叉排序樹的性質： 按中序遍歷二叉排序樹，所得到的中序遍歷序列是一個遞增有序序列。
基本介紹
- 中文名：二叉排序樹查找
- 外文名：Binary Search Tree
- 是一種：動態樹表
- 結構：數據
二叉排序樹的插入:,二叉排序樹生成：,二叉排序樹查找的程式實現:,
二叉排序樹的插入:
在二叉排序樹中插入新結點，要保證插入後的二叉樹仍符合二叉排序樹的定義。
插入過程：若二叉排序樹為空，則待插入結點*S作為根結點插入到空樹中；
當非空時，將待插結點關鍵字S->key和樹根關鍵字t->key進行比較，
若s->key = t->key,則無須插入，若s->key< t->key,則插入到根的左子樹中，
若s->key> t->key,則插入到根的右子樹中。而子樹中的插入過程和在樹中的插入過程相同，
如此進行下去，直到把結點*s作為一個新的樹葉插入到二叉排序樹中，或者直到發現樹已有相同關鍵字的結點為止。
二叉排序樹生成：
從空的二叉排序樹開始，經過一系列的查找插入操作以後，生成了一棵二叉排序樹。
說明：
① 每次插入的新結點都是二叉排序樹上新的葉子結點。
② 由不同順序的關鍵字序列，會得到不同二叉排序樹。
③ 對於一個任意的關鍵字序列構造一棵二叉排序樹，其實質上對關鍵字進行排序。
二叉排序樹查找的程式實現:
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個結點的二叉排序樹的平均查找長度和樹的形態有關。
最好的情況是： 二叉排序樹和二叉判定樹形態相同。
最壞的情況是： 二叉排序樹為單支樹，這時的平均查找長度和順序查找時相同。
最壞情況示例
就平均性能而言，二叉排序樹上的查找和二分查找相差不大，並且二叉排序樹上的插入和刪除結點十分方便，無須大量移動結點。
