什麼是二叉搜尋樹
二叉搜尋樹（BST，Binary Search Tree）， 也稱二叉排序樹或二叉查找樹 。一棵二叉樹，可以為空；如果不為空，滿足以下性質：
- 非空左子樹的所有鍵值小于其根結點的鍵值(/關鍵字）。
- 非空右子樹的所有鍵值大于其根結點的鍵值。
- 左、右子樹都是二叉搜尋樹。
- 注意：二叉排序樹中沒有相同關鍵字的結點。對二叉搜尋樹進行中序周遊可以得到按關鍵字排序的有序序列。*
//在讨論二叉排序樹上的運算之前,定義其節點的類型如下：
typedef int keyType
typedef struct node //記錄類型
{ KeyType key; //關鍵字項
InfoType data; //其他資料域
struct node *lchild,*rchild; //左右孩子指針
}
BSTNode;
二叉搜尋樹的指定結點的查找
顧名思義，這種二叉樹就是用來查找的。
因為二叉排序樹可看做是一個有序表，是以在二叉排序樹上進行查找，和二分查找類似,也是一個逐漸縮小查找範圍的過程。
查找從根結點開始，如果樹為空，傳回NULL 。
若搜尋樹非空，則根結點關鍵字和X進行比較，并進行不同處理：
若X小于根結點鍵值，隻需在左子樹中繼續搜尋；如果X大于根結點的鍵值，在右子樹中進行繼續搜尋； 若兩者比較結果是相等，搜尋完成，傳回指向此結點的指針。
//遞歸
BSTNode *SearchBST(BSTNode *bt,KeyType k)
{ if(bt==NULL || bt->key==k) //遞歸終結條件
return bt;
if (k<bt->key)
return SearchBST(bt->lchild,k); //在左子樹中遞歸查找
else return SearchBST(bt->rchild,k); //在右子樹中遞歸查找
}
由于非遞歸函數的執行效率高，可将“尾遞歸”函數改為疊代函數 ：
//非遞歸
BSTNode *SearchBST1(BSTNode *bt,KeyType k)
{
while (bt!=NULL)
{
if (k==bt->key)
return bt;
else if (k<bt->key)
bt=bt->lchild; //在左子樹中遞歸查找
else
bt=bt->rchild; //在左子樹中遞歸查找
}
return NULL; //沒有找到傳回NULL
}
注：查找的效率決定于樹的高度
查找最大和最小元素
按照性質，最大元素一定是在樹的最右分枝的端結點上 ；最小元素一定是在樹的最左分枝的端結點上 。參考代碼如下，按英文意思進行了解即可：
//查找最小元素的遞歸函數
Position FindMin( BinTree BST )
{
if( !BST )
return NULL; /*空的二叉搜尋樹，傳回NULL*/
else if( !BST->Left ) return BST; /*找到最左葉結點并傳回*/
else return FindMin( BST->Left ); /*沿左分支繼續查找*/ }
//查找最大元素的疊代函數
Position FindMax( BinTree BST )
{
if(BST)
while( BST->Right )
BST = BST->Right; /*沿右分支繼續查找，直到最右葉結點*/
return BST;
}
二叉搜尋樹的插入
關鍵是要找到元素應該插入的位置。
插入過程：
（1）若二叉排序樹T為空，則建立一個key域為k的節點，将它作為根節點；
（2）否則将k和根節點的關鍵字比較，若兩者相等，則說明樹中已有此關鍵字k，無須插入，直接傳回0；
（3）若kkey，則将k插入根節點的左子樹中。
（4）否則将它插入右子樹
int InsertBST(BSTNode *&p,KeyType k) //在以*p為根節點的BST中插入一個關鍵字為k的節點。插入成功傳回1,否則傳回0
{
if(p==NULL) //原樹為空, 新插入的記錄為根節點
{
p=(BSTNode*)malloc(sizeof(BSTNode));
p->key=k;
p->lchild=p->rchild=NULL;
return 1;
}
else if (k==p->key) //存在相同關鍵字的節點,傳回0
return 0;
else if (k<p->key) return InsertBST(p->lchild,k); //插入到左子樹中
else return InsertBST(p->rchild,k); //插入到右子樹中
}
二叉搜尋樹的生成
二叉排序樹的生成，是從一個空樹開始，每插入一個關鍵字,就調用一次插入算法将它插入到目前已生成的二叉排序樹中。
BSTNode *CreatBST(KeyType A[],int n) //傳回樹根指針
{
BSTNode *bt=NULL; //初始時bt為空樹
int i=0;
while (i<n)
{
InsertBST(bt,A[i]); //将A[i]插入二叉排序樹T中
i++;
}
return bt; //傳回建立的二叉排序樹的根指針
}
任何節點插入到二叉排序樹時，都是以葉子節點插入的。
**二叉搜尋樹的删除 **
這個過程是最複雜的。
1.①被删除的節點是葉子節點：直接删去該節點。其雙親節點中相應指針域的值改為“空”
②被删除的節點隻有左子樹或者隻有右子樹，用其左子樹或者右子樹代替它。其雙親節點的相應指針域的值改為 “指向被删除節點的左子樹或右子樹”。
③被删除的節點既有左子樹，也有右子樹：以其前驅替代之，然後再删除該前驅節點。前驅是左子樹中最大的節點
int DeleteBST(BSTNode *&bt,KeyType k) //在bt中删除關鍵字為k的節點
{
if(bt==NULL) return 0; //空樹删除失敗
else
{
if (k<bt->key)
return DeleteBST(bt->lchild,k);//遞歸在左子樹中删除為k的節點
else if (k>bt->key) return DeleteBST(bt->rchild,k);//遞歸在右子樹中删除為k的節點
else
{
Delete(bt); //調用Delete(bt)函數删除*bt節點
return 1;
}
}}
void Delete(BSTNode *&p) //從二叉排序樹中删除*p節點
{
BSTNode *q;
if(p->rchild==NULL) //*p節點沒有右子樹的情況
{
q=p;
p=p->lchild; //其左子樹的根節點放在被删節點的位置上
free(q);
}
else if (p->lchild==NULL) //*p節點沒有左子樹
{
q=p;
p=p->rchild; //其右子樹的根節點放在被删節點的位置
free(q);
}
else Delete1(p,p->lchild); //*p節點既有左子樹又有右子樹的情況
}
void Delete1(BSTNode *p,BSTNode *&r) //當被删*p節點有左右子樹時的删除過程
{
BSTNode *q;
if (r->rchild!=NULL) Delete1(p,r->rchild); //遞歸找最右下節點
else //找到了最右下節點*r
{
p->key=r->key; //将*r的關鍵字值賦給*p
q=r;
r=r->lchild; //将左子樹的根節點放在被删節點的位置上
free(q); //釋放原*r的空間
}
}
2.另一種類似做法：
考慮三種情況：
①要删除的是葉結點：直接删除，并再修改其父結點指針—置為NULL ；
②要删除的結點隻有一個孩子結點: 将其父結點的指針指向要删除結點的孩子結點 ；
③要删除的結點有左、右兩棵子樹： 用另一結點替代被删除結點：右子樹的最小元素 或者 左子樹的最大元素 ；取右子樹中的最小元素替代 ，取左子樹中的最大元素替代 ；
BinTree Delete( ElementType X, BinTree BST )
{
Position Tmp;
if( !BST )
printf("要删除的元素未找到");
else if( X < BST->Data )
BST->Left = Delete( X, BST->Left); /* 左子樹遞歸删除 */
else if( X > BST->Data )
BST->Right = Delete( X, BST->Right); /* 右子樹遞歸删除 */
else /*找到要删除的結點 */
if( BST->Left && BST->Right )
{ /*被删除結點有左右兩個子結點 */
Tmp = FindMin( BST->Right ); /*在右子樹中找最小的元素填充删除結點*/
BST->Data = Tmp->Data;
BST->Right = Delete( BST->Data, BST->Right); /*在删除結點的右子樹中删除最小元素*/
}
else { /*被删除結點有一個或無子結點*/
Tmp = BST;
if( !BST->Left ) /* 有右孩子或無子結點*/
BST = BST->Right;
else if( !BST->Right ) /*有左孩子或無子結點*/
BST = BST->Left;
free( Tmp );
}
return BST;
}
二叉查找樹結構由于樹的深度過大而造成磁盤I/O讀寫過于頻繁，進而導緻查詢效率低下.那麼如何提高效率，即如何避免磁盤過于頻繁的多次查找呢？根據磁盤查找存取的次數往往由樹的高度所決定，是以，隻要我們通過某種較好的樹結構減少樹的結構盡量減少樹的高度。這樣的樹就是：平衡二叉樹
各種樹
平衡二叉樹
B-和B+樹的定義、性質特點、舉例說明
線索二叉樹
哈夫曼樹Huffman Tree