1、定義
二叉搜索樹又稱二叉查找樹，亦稱為二叉排序樹。設(shè)x為二叉查找樹中的一個(gè)節(jié)點(diǎn)，x節(jié)點(diǎn)包含關(guān)鍵字key，節(jié)點(diǎn)x的key值記為key[x]。如果y是x的左子樹中的一個(gè)節(jié)點(diǎn)，則key[y] <= key[x]；如果y是x的右子樹的一個(gè)節(jié)點(diǎn)，則key[y] >= key[x]。
2、性質(zhì)
（1）若左子樹不空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值；
（2）若右子樹不空，則右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；
（3）左、右子樹也分別為二叉搜索樹；
如圖1為一顆二叉搜索樹
圖2所示不是一顆二叉搜索樹
3、創(chuàng)建二叉樹
現(xiàn)有序列：A = {61, 87, 59, 47, 35, 73, 51, 98, 37, 93}。
根據(jù)序列構(gòu)造二叉搜索樹過程如下：
i = 0；A[0] = 61；作為根節(jié)點(diǎn)；
i = 1，A[1] = 87，87 > 61，且節(jié)點(diǎn)61右孩子為空，故81為61節(jié)點(diǎn)的右孩子；
i = 2，A[2] = 59，59 < 61，且節(jié)點(diǎn)61左孩子為空，故59為61節(jié)點(diǎn)的左孩子；
i = 3，A[3] = 47，47 < 59，且節(jié)點(diǎn)59左孩子為空，故47為59節(jié)點(diǎn)的左孩子；
以此類推，構(gòu)建完畢后，如圖3
4、查找
4.1、查找步驟
（1）如果樹是空的，則查找結(jié)束，無匹配。
（2）如果被查找的值和節(jié)點(diǎn)的值相等，查找成功。
（3）如果被查找的值小于節(jié)點(diǎn)的值，遞歸查找左子樹，
（4）如果被查找的值大于節(jié)點(diǎn)的值，遞歸查找右子樹，
4.2、代碼
/* 遞歸查找二叉排序樹T中是否存在key, */
/* 指針f指向T的雙親，其初始調(diào)用值為NULL */
/* 若查找成功，則指針p指向該數(shù)據(jù)元素節(jié)點(diǎn)，并返回TRUE */
/* 否則指針p指向查找路徑上訪問的最后一個(gè)節(jié)點(diǎn)并返回FALSE */
bool searchBST(BSTNode* T, int key, BSTNode* f, BSTNode **p)
{
if (!T) /* 查找不成功 */
{
*p = f;
return false;
}
else if (key == T->key) /* 查找成功 */
{
*p = T;
return true;
}
else if (key < T->key)
return searchBST(T->lchild, key, T, p); /* 在左子樹中繼續(xù)查找 */
else
return searchBST(T->rchild, key, T, p); /* 在右子樹中繼續(xù)查找 */
}
5、插入
5.1、插入過程
（1）先檢測(cè)該元素是否在樹中已經(jīng)存在。如果已經(jīng)存在，則不進(jìn)行插入；
（2）若元素不存在，則進(jìn)行查找過程，并將元素插入在查找結(jié)束的位置。
5.2圖解過程
6、平衡二叉樹
6.1、定義
二叉搜索樹一定程度上可以提高搜索效率，但是當(dāng)原序列有序，例如序列A = {1，2，3，4，5，6}，構(gòu)造二叉搜索樹如圖8。依據(jù)此序列構(gòu)造的二叉搜索樹為右斜樹，同時(shí)二叉樹退化成單鏈表，搜索效率降低為O(n)。
在此二叉搜索樹中查找元素6需要查找6次。
二叉搜索樹的查找效率取決于樹的高度，因此保持樹的高度最小，即可保證樹的查找效率。同樣的序列A，改為圖9方式存儲(chǔ)，查找元素6時(shí)只需比較3次，查找效率提升一倍。
總結(jié)：可以看出當(dāng)節(jié)點(diǎn)數(shù)目一定，保持樹的左右兩端保持平衡，樹的查找效率最高。這種左右子樹的高度相差不超過1的樹為平衡二叉樹。
6.2、平衡因子
定義：某節(jié)點(diǎn)的左子樹與右子樹的高度(深度)差即為該節(jié)點(diǎn)的平衡因子（BF,Balance Factor），平衡二叉樹中不存在平衡因子大于1的節(jié)點(diǎn)。在一棵平衡二叉樹中，節(jié)點(diǎn)的平衡因子只能取-1、1或者0。
6.3 左旋與右旋
左旋：
如圖10所示的平衡二叉樹
如在此平衡二叉樹插入節(jié)點(diǎn)62，樹結(jié)構(gòu)變?yōu)椋?/p>
可以得出40節(jié)點(diǎn)的左子樹高度為1，右子樹高度為3，此時(shí)平衡因子為-2，樹失去平衡。為保證樹的平衡，此時(shí)需要對(duì)節(jié)點(diǎn)40做出旋轉(zhuǎn)，因?yàn)橛易訕涓叨雀哂谧笞訕?，?duì)節(jié)點(diǎn)進(jìn)行左旋操作，流程如下：
（1）節(jié)點(diǎn)的右孩子替代此節(jié)點(diǎn)位置
（2）右孩子的左子樹變?yōu)樵摴?jié)點(diǎn)的右子樹
（3）節(jié)點(diǎn)本身變?yōu)橛液⒆拥淖笞訕?/p>
圖解過程：
右旋：
右旋操作與左旋類似，操作流程為：
（1）節(jié)點(diǎn)的左孩子代表此節(jié)點(diǎn)
（2）節(jié)點(diǎn)的左孩子的右子樹變?yōu)楣?jié)點(diǎn)的左子樹
（3）將此節(jié)點(diǎn)作為左孩子節(jié)點(diǎn)的右子樹。
圖解過程：
