1.二叉排序樹的定義
二叉排序樹：
1)或者是一棵空樹。
2)或者是具有下列性質的二叉樹：
[1]若它的左子樹不空，則左子樹上所有的結點的值都小于它的根節點的值；
[2]若它的右子樹不空，則右子樹上所有的結點的值都大于它的根節點的值；
[3]它的左子樹、右子樹也都分别是二叉排序樹。
2.二叉排序樹的查找
二叉排序樹又稱為二叉查找樹。查找過程和次優二叉樹查找類似。即當二叉排序樹不空時，首先将給定的值和根節點的值比較，若相等，則查找成功，否則将依據給定值和根節點的關鍵字之間的大小關系，分别在左子樹或右子樹上繼續進行查找。通常，采用二叉鍊作為二叉排序樹的存儲結構。查找算法如下所示：
//二叉排序樹查找
BiTree SearchBST(BiTree T, KeyType key) {
//在根指針T所指二叉排序樹中遞歸地查找某關鍵字等于key的資料元素。
//若查找成功，則傳回指向該資料元素結點的指針，否則傳回空指針。
if (!T || (key == T->data.key) {//如果該樹為空，或者給定的值等于根節點的值，則傳回根節點指針
return T;
}
else if(key < T->data.key) {//小于根節點的值，則繼續在左子樹中查找
return SearchBST(T->lchild, key);
}
else (key > T->data.key) {//大于根節點的值，則繼續在右子樹中查找
return SearchBST(T->rchild, key);
}
}
3.二叉排序樹的插入
二叉排序樹是一種動态樹表。其特點是，樹的結構通常不是一次性生成的，而是在查找過程中，當樹中不存在關鍵字等于給定的值時再進行插入。新插入的結點一定是一個新添加的葉子結點，并且是查找不成功時查找路徑上通路的最後一個結點的左孩子或右孩子結點。下面的算法時将二叉排序樹的查找算法改成當查找不成功時，傳回插入位置：
//二叉排序樹查找，當查找不成功時，傳回插入位置
BiTree SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p) {
//在根指針T所指二叉排序樹中遞歸地查找某關鍵字等于key的資料元素。
//若查找成功，則指針p指向該資料元素結點，并傳回TRUE，
//若查找不成功，則傳回指針p指向查找路徑上的最後一個結點并傳回FALSE，
//指針f指向T的雙親，其初始調用值為NULL
if (!T) {//如果該樹為空，則傳回根節點指針 ，查找失敗
p = f;
return FALSE;
}
else if (key == T->data.key) {//查找成功
p = T;
return TRUE;
}
else if (key < T->data.key) {//小于根節點的值，則繼續在左子樹中查找
return SearchBST(T->lchild, key, T, p);
}
else (key > T->data.key) {//大于根節點的值，則繼續在右子樹中查找
return SearchBST(T->rchild, key, T, p);
}
}
二叉排序樹的插入算法：
//二叉排序樹的插入算法
Status InsertBST(BiTree &T, ElemType e) {
//當二叉排序樹T中不存在關鍵字等于e.key的資料元素時，插入e并傳回TRUE，
//否則傳回FALSE
if (!(SearchBST(T, e.key, NULL, p))) {//若查找不成功，指針p指向查找路徑上的最後一個結點
//結點初始化
s = (BiTree)malloc(sizeof(BiTree));
s->data = e;
s->lchild = NULL;
s->rchild = NULL;
if (!p) {//如果該樹T是一棵空樹，被插入的結點*s為新的根節點
T = s;
}
else if (e.key < p->data.key) { //被插入的結點*s為左孩子
p->lchild = s;
}
else {//被插入的結點*s為右孩子
p->rchild = s;
}
return TRUE;
}
else { //若該樹中已經存在關鍵字相同的結點，則不再插入該結點
return FALSE;
}
}
4.案例分析
設查找的關鍵字序列為：45,24,53,45,12,24,90，共7個關鍵字，其中45，24分别有兩個，則在插入時，根據二叉排序樹的插入算法，如果該關鍵字已經存在，則不再插入。下面是該二叉排序樹的圖：
紅色的編号分别是結點插入的順序編号。
該二叉排序樹的中序周遊序列是：12,24,45,53,90， 從該序列中可以看出二叉排序樹的中序周遊是一個關鍵字非遞減的有序序列。每次插入的結點都是二叉排序樹上新的葉子結點，則在進行插入操作時，不需要移動其他結點，僅需改動某個結點的指針，由空變為非空即可。這就相當于在一個序列中，插入一個元素，但是不需要移動其他元素，這樣的話效率就更高。表明二叉排序樹既擁有類似于折半查找的特性，又采用了連結清單作為存儲結構，是以是一種動态查找表的一種适宜表示。
5.二叉排序樹的删除
二叉排序樹在删除一個記錄之後，需要保持任然還是一棵二叉排序樹，如果删除一個記錄後破壞了二叉排序樹，則還需要重建這棵二叉排序樹。
假設删除結點*p，其雙親是*f，假設結點p是f的左孩子：
則有以下三種情況：
a.p結點是葉子結點。則直接删除結點p不會破壞二叉排序樹。
b.p結點隻有左子樹或右子樹，則隻需要将該結點的左子樹或右子樹直接成為f結點的左孩子即可，這樣任然還是一棵二叉排序樹。
c.p結點既有左子樹又有右子樹。這種情況删除p結點之後，會破壞二叉排序樹，需要重建。可以有以下兩種方法。
[1]第一種方法是将p的左子樹成為f的左子樹，p的右子樹成為f的右子樹；
[2]第二種方法是将p的直接前驅或直接後繼代替p，然後再删除其直接前驅或直接後繼。
二叉排序樹的删除操作代碼：
statue Delete(BiTree &p) {
//從二叉排序樹删除節點P，并重接他的左子樹或右子樹
if (!p->rchild) { //右子樹為空則隻需要重接他的左子樹
q = p;
p = p->lchild;
free(q);
}
else if (!p->lchild) { //左子樹為空，則隻需要重接他的右子樹
q = p;
p = p->rchild;
free(q);
}
else { //左右子樹均不空
q = p;
s = p->lchild;
while (s->rchild) { //轉左，然後向右到盡頭
p->data = s->data;
if (q != p) { //重接*q的右子樹
q->rchild = s->lchild;
} else { //重接*q 的左子樹
q->lchild = s->lchild;
}
}
delete s;
}
return TRUE;
}
status DeleteBST(BiTree &T, keyType key) {
//若二叉排序樹T中存在關鍵字等于key的資料元素時，則删除該資料元素結點，并傳回TRUE；否則傳回FALSE
if (!T) {
return FALSE;
} else {
if (key == T->data.key) { //找到關鍵字等于key的資料元素
return Delete(T);
} else if (key < T->data.key) { //關鍵字小于根節點，則向左子樹繼續查找
return DeleteBST(T->lchild, key);
} else { //關鍵字大于根節點，則向右繼續查找
return DeleteBST(T->rchild, key);
}
}
}
6.二叉排序樹的查找分析
在二叉排序樹上查找關鍵字等于給定值的結點的過程，恰是一條從根節點到該結點的路徑的過程，和給定值比較的關鍵字的個數等于路徑長度加1（因為比較的最後一個結點是葉子結點，仔細想想就知道）。是以，和折半查找類似，與給定值比較的關鍵字的個數不超過樹的深度。
顯然，二叉排序樹的關鍵字序列決定了二叉排序樹的形态，而形态又決定了查找長度。如以下兩棵二叉排序樹：
平均查找長度ASL = (1 + 2 + 2 + 3 + 3 + 3) / 6 = 14 / 6
平均查找長度ASL = （1 + 2 + 3 + 4 + 5 + 6）/ 6 = 21 / 6
以上兩個二叉排序樹的關鍵字序列的值一樣，但是由于排序的序列不一樣，導緻形成的二叉排序樹的形狀不一樣，又導緻其平均查找長度不一樣，是以二叉排序樹的平衡查找長度和樹的形狀有關。
從第二棵樹可知，當插入的關鍵字有序時，構成的二叉排序樹是一棵單支樹。
單支樹的深度為n，其平均查找長度為(n+1)/2，這是最差的情況。
顯然，最好的情況是二叉排序樹的形态和折半查找的判定樹相同，其平均查找長度和log2^n成正比。