二叉排序樹的查找屬於動態查找的范疇,根據查找過程中是否對表進行修改,可以把查找分為靜態查找和動態查找。動態查找表的特點是:表結構本身是在查找過程中動態生成的,即對於給定的key值,若表中存在其關鍵字等於key的記錄,則查找成功並返回,否則插入關鍵字等於key的記錄。
二叉排序樹或者是一顆空樹,或者是具有下列性質的二叉樹:
(1)若它的左子樹非空,則左子樹上的所有結點的值均小於根節點的值;
(2)若它的右子樹非空,則右子樹上的所有結點的值均大於根節點的值;
(3)它的左右子樹也分別為二叉排序樹;
1、二叉排序樹的數據結構
typedef struct node { short key; struct node *rchild,*lchild; } BSTNode,*BSTree;
2、二叉排序樹的插入和生成
已知一個關鍵字值為key的節點s,若將其插入到二叉排序樹中,只要保證插入後仍符合二叉排序樹的定義即可,插入可以用一下方法。
(1)若二叉排序樹為空樹,則key稱為二叉排序樹的根;
(2)若二叉排序樹非空,則將key與二叉排序樹的根比較,如果key值等於根節點,則停止插入;如果key值小於根節點的值,則將key插入左子樹;如果key值大於根節點的值,則將key插入右子樹;
二叉樹的插入算法如下:
void InsertBST(BSTree* bst,short key) { BSTree s; if(*bst==NULL) //遞歸結束條件;該結點為空時創建結點; { s=(BSTree)malloc(sizeof(BSTNode)); s->key=key; s->lchild=NULL; s->rchild=NULL; *bst=s; } else if(key<(*bst)->key) { InsertBST(&((*bst)->lchild),key); } else if(key>(*bst)->key) { InsertBST(&((*bst)->rchild),key); } } /****************** * 根據二叉排序樹的插入算法可以創建一顆二叉排序樹; ****************************/ void CreateBST(BSTree* bst) { char key; *bst=NULL; scanf("%c",&key); while (key!='?') //輸入字符的結束是'?'; { InsertBST(bst,key); scanf("%c",&key); } }
3、二叉排序樹的刪除
在二叉排序樹中刪除一個結點比插入一個結點要困難,除非是葉子結點,否則必須考慮部分鏈的對接,以保證刪除一個結點後能使剩下的結點仍是一顆二叉排序樹。
假設要刪除的結點為P,其雙親結點為F,且不失一般性,並設結點P是結點F的左孩子(右孩子情況類似)。如下圖所示:(注:下圖截至數據結構書中)。
下面分三種情況進行討論:
(1)若P為葉子節點,刪除P後只需修改雙親節點的指針即可;
(2)如果P的左子樹為空或者P的右子樹為空,此時只需令其左右子樹PL,PR成為其雙親結點F的左右子樹即可;
(3)若P的左右子樹均不為空,如圖8.7(a)所示:此時有兩種處理方法。<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+ICC3vbeoMaO6ytfPyNXStb1QveG149Ta1tDQ8tDywdDW0LXE1rG908ewx/1TveG146OsyOfNvDguN6OoYqOpy/nKvqOsyLu6872rULXE1/PX08r3uMTOqka1xNfz19PK96OsULXE09LX08r3uMTOqlO1xNPS19PK96O7PC9wPgo8cD4gIEYtPmxjaGlsZD1QLT5sY2hpbGQ7Uy0+cmNoaWxkPVAtPnJjaGlsZDtmcmVlKFApO73hufvI5828OC43o6hjo6nL+cq+o7rS8s6qULXE09K94bXjyv0mIzIwNTQwO7HIU7XEyv0mIzIwNTQwO7Tzo6y5yrK7u+G4xLHktv6y5sXF0PLK97XE0NTWyjs8L3A+CjxwPiC3vbeoMqO6ytfPyNXStb1QveG149Ta1tDQ8tDywdDW0LXE1rG908ewx/1TveG146OsyOfNvDguN6OoYqOpy/nKvqOsyLu689PDU73hteO1xCYjMjA1NDA7tPrM5lC94bXjtcQmIzIwNTQwO6Os1Nm9q1O94bXjyb6z/SzUrVO94bXjtcTX89fTyve4xM6qy6vH1zwvcD4KPHA+IL3hteNRveG147XE09LX08r3o7tQLT5kYXRhPVMtPmRhdGE7US0+cmNoaWxkPVMtPmxjaGlsZDtmcmVlKFMpoaO94bn7yOfNvDguN6OoZKOpy/nKvqGjPC9wPgo8cD6+38zly+O3qMPoyvbI58/Co7o8L3A+CjxwPjxwcmUgY2xhc3M9"brush:java;">void DelBST(BSTree *t,short key)
{
BSTNode *p,*f,*s,*q;
p=*t;
f=NULL;
while (p) //查找關鍵字為key的待刪節點;
{
if(p->key==key)
{
break;
}
f=p; //f指向p節點的雙親節點;
if(p->key>key)
{
p=p->lchild;
}
else
{
p=p->rchild;
}
}
if(p==NULL) //如果沒有找到直接返回;
{
return;
}
if(f==NULL) //如果p是原二叉排序樹的根;
{
free(p);
*t=NULL;
return;
}
if(p->lchild==NULL&&p->rchild==NULL) //如果p沒有左右子樹;
{
if(f->lchild==p)
{
f->lchild=NULL;
}
else
{
f->rchild=NULL;
}
free(p);
}
else if(p->lchild==NULL&&p->rchild!=NULL) //如果p的左子樹為空,右子樹不為空;
{
if(f->lchild==p)
{
f->lchild=p->rchild; //把p的右子樹鏈接到父親的左鏈上;
}
else
{
f->rchild=p->rchild; //把p的右子樹鏈接到父親的右鏈上;
}
free(p);
}
else if(p->lchild!=NULL&&p->rchild==NULL) //如果p的左子樹不為空,右子樹為空;
{
if(f->lchild==p)
{
f->lchild=p->lchild; //把p的右子樹鏈接到父親的左鏈上;
}
else
{
f->rchild=p->lchild; //把p的右子樹鏈接到父親的右鏈上;
}
free(p);
}
else if(p->lchild!=NULL&&p->rchild!=NULL) //如果p的左右子樹都不為空;
{
q=p;
s=p->lchild; //s指向p的左節點;
while (s->rchild)
{
q=s;
s=s->rchild;
}
p->key=s->key; //把s節點的數據賦值給p節點;
if(p==q) //說明待刪除的p節點的左子節點下沒有右結點;
{
q->lchild=s->lchild; //把s節點的左子樹鏈接到q的左節點下;
}
else
{
q->rchild=s->lchild; //把s節點的左子樹鏈接到q的右節點下;
}
free(s);
}
}
4.二叉排序樹的查找
由二叉排序樹的定義可知,在二叉排序樹上進行查找與二分查找類似。即:當二叉排序樹不為空時,首先將給定值與根結點的關鍵值相比較,若相等,則查找成功。否則,將依據給定值和根節點關鍵值之間的大小關系,分別在左右子樹上繼續進行查找,其查找過程的算法如下:
BSTree SearchBST(BSTree bst,short key) { if(bst==NULL) { return NULL; } if(bst->key==key) { return bst; } else if(bst->key>key) { return SearchBST(bst->lchild,key); } else { return SearchBST(bst->rchild,key); } }
根據二叉排序樹的查找算法可以看出,二叉排序樹的查找和二分查找類似,和關鍵字比較次數不超過樹的深度,然而二分查找長度n的表判定樹是唯一的,而含有n個結點二叉排序樹卻不唯一。對於含有同樣關鍵字序列的一組結點,結點插入的先後次序不同,所構成的二叉排序樹的形態和深度不同。而二叉排序樹的平均查找長度ASL與二叉樹的形態相關,二叉排序樹的各分支越均衡,樹的深度越淺,其平均查找長度ASL越小。
就平均性能而言,二叉排序樹上的查找和二分查找相差不大,並且二叉排序樹上的插入和刪除結點十分方便,無需移動大量的結點。因此,對於需要經常做插入、刪除、查找運算的表,宜采用二叉排序樹,因此二叉排序樹又稱為二叉查找樹。
6、總結
上面是我在精讀數據結構時,對二叉排序樹的一點總結,也參考了相關的書籍,望各位讀者多多指教。