1.二叉搜索樹(BST，Binary Search Tree)， 也稱二叉排序樹或二叉查找樹

二叉搜索樹:一棵二叉樹，可以為空;如果不為空，滿足以下性質(zhì):

1. 非空左子樹的所有鍵值小于其根結(jié)點(diǎn)的鍵值。
2. 非空右子樹的所有鍵值大于其根結(jié)點(diǎn)的鍵值。
3. 左、右子樹都是二叉搜索樹。

2.二叉搜索樹的查找操作:Find

Position Find( ElementType X, BinTree BST ) {
if( !BST ) return NULL; /*查找失敗*/ 
if( X > BST->Data )
return Find( X, BST->Right ); /*在右子樹中繼續(xù)查找*/
Else if( X < BST->Data )
return Find( X, BST->Left ); /*在左子樹中繼續(xù)查找*/
else /* X == BST->Data */
return BST; /*查找成功，返回結(jié)點(diǎn)的找到結(jié)點(diǎn)的地址*/
}

// 用尾遞歸，效率低

由于非遞歸函數(shù)的執(zhí)行效率高，可將“尾遞歸”函數(shù)改為迭代函數(shù)

Position IterFind( ElementType X, BinTree BST ) {
    while( BST ) {
        if( X > BST->Data )
BST = BST->Right; /*向右子樹中移動，繼續(xù)查找*/ 
else if( X < BST->Data )
BST = BST->Left; /*向左子樹中移動，繼續(xù)查找*/ 
else /* X == BST->Data */
return BST; /*查找成功，返回結(jié)點(diǎn)的找到結(jié)點(diǎn)的地址*/ return NULL; /*查找失敗*/
} 
return NULL
}

3.查找最大值和最小值
最大元素一定是在樹的最右分枝的端結(jié)點(diǎn)上
最小元素一定是在樹的最左分枝的端結(jié)點(diǎn)上

// 查找最小值的遞歸函數(shù)
Position FindMin( BinTree BST )
{
if( !BST ) return NULL; /*空的二叉搜索樹，返回NULL*/ 
else if( !BST->Left )
 return BST; /*找到最左葉結(jié)點(diǎn)并返回*/
else
return FindMin( BST->Left ); /*沿左分支繼續(xù)查找*/
}

// 查找最大值的迭代函數(shù)
Position FindMax( BinTree BST ){
if(BST )
while( BST->Right ) BST = BST->Right;/*沿右分支繼續(xù)查找，直到最右葉結(jié)點(diǎn)*/
return BST;
}

4.二叉搜索樹的插入
關(guān)鍵是要找到元素應(yīng)該插入的位置， 可以采用與Find類似的方法

BinTree Insert( ElementType X, BinTree BST ) {
if( !BST ){ /*若原樹為空，生成并返回一個結(jié)點(diǎn)的二叉搜索樹*/
BST = malloc(sizeof(struct TreeNode)); 
BST->Data = X;
BST->Left = BST->Right = NULL;
}else /*開始找要插入元素的位置*/
 if( X < BST->Data )
BST->Left = Insert( X, BST->Left);
/*遞歸插入左子樹*/ 
else if( X > BST->Data )
BST->Right = Insert( X, BST->Right);
/*遞歸插入右子樹*/ /*else  X已經(jīng)存在，什么都不做 */
return BST;
}

5. 二叉搜索樹的刪除
   有3種情況：
   要刪除的是葉結(jié)點(diǎn):直接刪除，并再修改其父結(jié)點(diǎn)指針---置為NULL
   要刪除的結(jié)點(diǎn)只有一個孩子結(jié)點(diǎn): 將其父結(jié)點(diǎn)的指針指向要刪除結(jié)點(diǎn)的孩子結(jié)點(diǎn)
   要刪除的結(jié)點(diǎn)有左、右兩棵子樹: 用另一結(jié)點(diǎn)替代被刪除結(jié)點(diǎn):右子樹的最小元素 或者 左子樹的最大元素

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 /*找到要刪除的結(jié)點(diǎn) */
if( BST->Left && BST->Right ) { /*被刪除結(jié)點(diǎn)有左右兩個子結(jié)點(diǎn) */ 
Tmp = FindMin( BST->Right );
/*在右子樹中找最小的元素填充刪除結(jié)點(diǎn)*/ 
BST->Data = Tmp->Data;
BST->Right = Delete( BST->Data, BST->Right);
/*在刪除結(jié)點(diǎn)的右子樹中刪除最小元素*/ } 
else { /*被刪除結(jié)點(diǎn)有一個或無子結(jié)點(diǎn)*/
Tmp = BST;
if( !BST->Left ) /* 有右孩子或無子結(jié)點(diǎn)*/
BST = BST->Right;
else if( !BST->Right ) /*有左孩子或無子結(jié)點(diǎn)*/
BST = BST->Left;
free( Tmp );
} 
return BST;
}