二叉排序樹（BST），也稱二叉查找樹。
二叉排序樹或者為空樹，或者為非空樹，當為非空樹時有如下特點：
1、若左子樹非空，則右子樹所有的結點關鍵字值均小于根節(jié)點的關鍵字。
2、若右子樹非空，則右子樹所有的結點關鍵字值均大于根節(jié)點的關鍵字。
3、左、右子樹本身也分別是一課二叉排序樹。
* 二叉排序樹的中序遍歷序列是一個遞增的有序序列。
查找
二叉樹非空時，查找根結點，若相等則查找成功；
若不等，則當小于根節(jié)點值時，查找左子樹；當大于根節(jié)點值時，查找右子樹。
當查找到葉子結點仍沒查找到相應的值，則查找失敗。
BSTNode *BST_Search(BiTree T,ElemType key,BSTNode *&p){
? ? ? ? p=null;
? ? ? ? while(T!=null&key!=T->data){
? ? ? ? ? ? ? ? p=T;
????????????????if(key>T->data)
? ? ? ? ? ? ? ? ? ? ? ? T = T->rchild;
? ? ? ? ? ? ? ? else
? ???????????????????????T = T->lchild;
????????}
? ? ? ? return T;
}
插入
如二叉排序樹為空，直接插入結點；
若二叉排序樹非空，當值小于根結點的時，插入左子樹；當值大于根結點時，插入右子樹；當值等于根結點時不進行插入。
int BST_Insert(BiTree &T,KeyType k){
? ? ? ? if(T==NULL)
? ? ? ? ? ? ? ? T = (BiTree)malloc(sizeof(BSTNode));
? ? ? ? ? ? ? ? T->date = k;
? ? ? ? ? ? ? ? T->lchild = T->rchild = null;
? ? ? ? ? ? ? ? return 1;
? ? ? ? else if(T->data==k)
? ? ? ? ? ? ? ? return 0;
? ? ? ? else if(?k >?T->data )
? ? ? ? ? ? ? ? return BST_Insert(T->rchild,k);
? ? ? ? else
? ? ? ? ? ? ? ? return BST_Insert(T->lchild,k);? ? ?
}
構造二叉排序樹
讀入一個元素并建立結點，若二叉樹為空，將其作為根結點；
若二叉樹排序樹非空，當值小于根結點時，插入左子樹；當值小于根結點時，插入右子樹；當值等于根結點時，不進行插入。
void Create_BST(BiTree &T,KeyType str[],int n){
? ? ? ? T=NULL;
? ? ? ? int i = 0;
? ? ? ? while(i<n){
? ? ? ? ? ? ? ? BST_Insert(T,str[i]);
? ? ? ? ? ? ? ? i++;
????????}
}????????
注：二叉排序樹的構建情況會因為str數(shù)組中數(shù)字排序的順序不一樣，而產(chǎn)生不一樣的效果。
刪除
1、若被刪除的結點是葉子結點，則直接刪除；
2、若被刪除結點z只有一棵子樹，則讓z的子樹成為z父結點的子樹，代替z結點；
3、若被刪除的結點z有兩棵子樹，則讓z的中序序列直接后繼代替z，并刪去直接后繼結點。
在二叉排序樹中刪除并插入某結點（結點值相同），得到的二叉排序樹是否與原來一致？
結論：可能相同，也可能不同。
查找效率
平均查找長度(ASL)取決于樹的高度。
