二叉排序樹的查找屬於動態查找的范疇，根據查找過程中是否對表進行修改，可以把查找分為靜態查找和動態查找。動態查找表的特點是：表結構本身是在查找過程中動態生成的，即對於給定的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）所示：此時有兩種處理方法。<喎?/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、總結
上面是我在精讀數據結構時，對二叉排序樹的一點總結，也參考了相關的書籍，望各位讀者多多指教。
