二叉排序樹又稱二叉查找樹，它是一種對排序和查找都很有用的特殊二叉樹。
（1）若它的左子樹不為空，則左子樹上的所有結點的值均小于它的根結點的值；
（2）若它的右子樹不為空，則右子樹上所有結點的值均小于它的根結點上的值；
（3）它的左右子樹本身也分别為二叉排序樹。
通過中序排列我們發現中序周遊的結果是結點的值是由低到高的。
二叉排序樹的 查找依然沿用前面介紹的順序查找和折半查找。
（1）若二叉排序樹為空，則查找失敗，則傳回空指針。
（2）若二叉排序樹非空，将給定值key與根結點的關鍵字t->data.key進行比較：
若key等于t->data.key,則查找成功，傳回根結點位址；
若key小于t->data.key，則進一步查找左子樹；
若key大于t->data.key，則進一步查找右子樹。
（1）若二叉排序樹為空，則待插入結點*s作為根結點插入到空樹中。
（2）若二叉排序樹非空，則将key與根結點的關鍵字t->data.key進行比較：
若key等于t->data.key，則停止插入；
若key小于t->data.key,則将*s插入左子樹；
若key大于t->data.key,，則将*s插入右子樹。
二叉排序樹的建立是從空的二叉排序樹開始，每輸入一個結點，經過查找操作，将新結點插入到目前二叉排序樹的合适位置。
（1）将二叉排序樹t初始化為空樹
（2）讀入一個關鍵字為key的結點，将此結點插入二叉排序樹t中。
（3）重複操作，直至讀入的關鍵字key是輸入結束标志。
注意:不同的的插入次序的序列生成不同形态的二叉排序樹
在二叉排序樹中删除一個結點，這是二叉排序樹中最有深度的操作。
若*p結點為葉子結點，即pl(左子樹)和pr(右子樹)均為空樹。由于删去葉子結點不破壞整棵樹的結構，則隻需修改其雙親結點的指針即可。
若*p結點隻有左子樹pl或右子樹pr，此時隻要令pl或pr直接成為其雙親結點*f的左子樹（當*p是左子樹）或右子樹（當*p是右子樹）即可，作此修改也不破壞二叉排序樹的特性。
若*p結點的左子樹和右子樹均不空。在删去*p之後，為保持其它元素之間的相對位置不變，可按中序周遊保持有序進行調整。比較好的做法是，找到*p的直接前驅（或直接後繼）*s，用*s來替換結點*p，然後再删除結點*s。
/* 若二叉排序樹t中存在關鍵字等于key的資料元素時，則删除該資料元素結點, */
/* 并傳回true；否則傳回false。 */
二叉排序樹的查找長度與二叉樹的形态有關，即
最好：log2n（形态均勻，與二分查找的判定樹相似）
最壞：（n+1）/2（單支數）
是以為了改善查找效率就引入我們接下來要學習的一種更優良的樹—-平衡二叉樹