二叉排序樹(Binary Sort Tree或Binary Search Tree) 的定義為：二叉排序樹或者是空樹，或者是滿足下列性質的二叉樹。
(1) ：若左子樹不為空，則左子樹上所有結點的值(關鍵字)都小於根結點的值；
(2) ：若右子樹不為空，則右子樹上所有結點的值(關鍵字)都大於根結點的值；
(3) ：左、右子樹都分別是二叉排序樹。
結論：若按中序遍歷一棵二叉排序樹，所得到的結點序列是一個遞增序列。
BST仍然可以用二叉鏈表來存儲
節點結構定義如下：
[cpp] <SPAN style="FONT-SIZE: 18px">struct BiTNode
{
int data;
struct BiTNode *lchild,*rchild;
};
typedef struct BiTNode BiTNode,*biTree;</SPAN>
struct BiTNode
{
int data;
struct BiTNode *lchild,*rchild;
};
typedef struct BiTNode BiTNode,*biTree;
一、二叉排序樹的查找
1 查找思想
首先將給定的K值與二叉排序樹的根結點的關鍵字進行比較：若相等：則查找成功；
①給定的K值小於BST的根結點的關鍵字：繼續在該結點的左子樹上進行查找；
② 給定的K值大於BST的根結點的關鍵字：繼續在該結點的右子樹上進行查找。
2 代碼實現
[cpp] <SPAN style="FONT-SIZE: 18px">biTree SearchBST(biTree T,int key)
{
//在根指針T所指的二叉排序樹中遞歸地查找某關鍵字等於key的數據元素
//若查找成功，則返回指向數據元素節點的指針，否則，返回空指針
if (T==NULL)
{
return NULL;
}
else
{
if (key==T->data)
{
return T;
}
else if (key<T->data)
{
return (SearchBST(T->lchild,key));
}
else
{
return(SearchBST(T->rchild,key));
}
}
}
</SPAN>
biTree SearchBST(biTree T,int key)
{
//在根指針T所指的二叉排序樹中遞歸地查找某關鍵字等於key的數據元素
//若查找成功，則返回指向數據元素節點的指針，否則，返回空指針
if (T==NULL)
{
return NULL;
}
else
{
if (key==T->data)
{
return T;
}
else if (key<T->data)
{
return (SearchBST(T->lchild,key));
}
else
{
return(SearchBST(T->rchild,key));
}
}
}
二、插入
1，插入思想
在BST樹中插入一個新結點x時，若BST樹為空，則令新結點x為插入後BST樹的根結點；否則，將結點x的關鍵字與根結點T的關鍵字進行比較：
①若相等：不需要插入；
② 若x.key<T->key：結點x插入到T的左子樹中；
③ 若x.key>T->key：結點x插入到T的右子樹中
2，代碼實現
[cpp] <SPAN style="FONT-SIZE: 18px">void InsertBST (biTree &T , int key)
{
if (T==NULL)
{
biTree x;
x=new BiTNode;
x->data=key;
x->lchild=x->rchild=NULL;
T=x;
cout<<"插入成功\n";
}
else
{
if (T->data==key)
{
cout<<"節點已存在\n"<<endl;
}
else if (key<T->data)
{
InsertBST(T->lchild,key);
}
else
{
InsertBST(T->rchild,key);
}
}
}</SPAN>
void InsertBST (biTree &T , int key)
{
if (T==NULL)
{
biTree x;
x=new BiTNode;
x->data=key;
x->lchild=x->rchild=NULL;
T=x;
cout<<"插入成功\n";
}
else
{
if (T->data==key)
{
cout<<"節點已存在\n"<<endl;
}
else if (key<T->data)
{
InsertBST(T->lchild,key);
}
else
{
InsertBST(T->rchild,key);
}
}
}
三、刪除
1，刪除思想
從BST樹上刪除一個結點，仍然要保證刪除後滿足BST的性質。設被刪除結點為p，其父結點為f ，刪除情況如下：
① 若p是葉子結點：直接刪除p，如圖9-5(b)所示。
② 若p只有一棵子樹(左子樹或右子樹)：直接用p的左子樹(或右子樹)取代p的位置而成為f的一棵子樹。即原來p是f的左子樹，則p的子樹成為f的左子樹；原來p是f的右子樹，則p的子樹成為f的右子樹
③ 若p既有左子樹又有右子樹：處理方法有以下兩種，可以任選其中一種。
◆ 用p的直接前驅結點代替p。即從p的左子樹中選擇值最大的結點s放在p的位置(用結點s的內容替換結點p內容)，然後刪除結點s。s是p的左子樹中的最右邊的結點且沒有右子樹，對s的刪除同②，如圖9-5(e)所示。
◆用p的直接後繼結點代替p。即從p的右子樹中選擇值最小的結點s放在p的位置(用結點s的內容替換結點p內容)，然後刪除結點s。s是p的右子樹中的最左邊的結點且沒有左子樹，對s的刪除同②
