1、定义
二叉搜索树又称二叉查找树，亦称为二叉排序树。设x为二叉查找树中的一个节点，x节点包含关键字key，节点x的key值记为key[x]。如果y是x的左子树中的一个节点，则key[y] <= key[x]；如果y是x的右子树的一个节点，则key[y] >= key[x]。
2、性质
（1）若左子树不空，则左子树上所有节点的值均小于它的根节点的值；
（2）若右子树不空，则右子树上所有节点的值均大于它的根节点的值；
（3）左、右子树也分别为二叉搜索树；
如图1为一颗二叉搜索树
图2所示不是一颗二叉搜索树
3、创建二叉树
现有序列：A = {61, 87, 59, 47, 35, 73, 51, 98, 37, 93}。
根据序列构造二叉搜索树过程如下：
i = 0；A[0] = 61；作为根节点；
i = 1，A[1] = 87，87 > 61，且节点61右孩子为空，故81为61节点的右孩子；
i = 2，A[2] = 59，59 < 61，且节点61左孩子为空，故59为61节点的左孩子；
i = 3，A[3] = 47，47 < 59，且节点59左孩子为空，故47为59节点的左孩子；
以此类推，构建完毕后，如图3
4、查找
4.1、查找步骤
（1）如果树是空的，则查找结束，无匹配。
（2）如果被查找的值和节点的值相等，查找成功。
（3）如果被查找的值小于节点的值，递归查找左子树，
（4）如果被查找的值大于节点的值，递归查找右子树，
4.2、代码
/* 递归查找二叉排序树T中是否存在key, */
/* 指针f指向T的双亲，其初始调用值为NULL */
/* 若查找成功，则指针p指向该数据元素节点，并返回TRUE */
/* 否则指针p指向查找路径上访问的最后一个节点并返回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); /* 在左子树中继续查找 */
else
return searchBST(T->rchild, key, T, p); /* 在右子树中继续查找 */
}
5、插入
5.1、插入过程
（1）先检测该元素是否在树中已经存在。如果已经存在，则不进行插入；
（2）若元素不存在，则进行查找过程，并将元素插入在查找结束的位置。
5.2图解过程
6、平衡二叉树
6.1、定义
二叉搜索树一定程度上可以提高搜索效率，但是当原序列有序，例如序列A = {1，2，3，4，5，6}，构造二叉搜索树如图8。依据此序列构造的二叉搜索树为右斜树，同时二叉树退化成单链表，搜索效率降低为O(n)。
在此二叉搜索树中查找元素6需要查找6次。
二叉搜索树的查找效率取决于树的高度，因此保持树的高度最小，即可保证树的查找效率。同样的序列A，改为图9方式存储，查找元素6时只需比较3次，查找效率提升一倍。
总结：可以看出当节点数目一定，保持树的左右两端保持平衡，树的查找效率最高。这种左右子树的高度相差不超过1的树为平衡二叉树。
6.2、平衡因子
定义：某节点的左子树与右子树的高度(深度)差即为该节点的平衡因子（BF,Balance Factor），平衡二叉树中不存在平衡因子大于1的节点。在一棵平衡二叉树中，节点的平衡因子只能取-1、1或者0。
6.3 左旋与右旋
左旋：
如图10所示的平衡二叉树
如在此平衡二叉树插入节点62，树结构变为：
可以得出40节点的左子树高度为1，右子树高度为3，此时平衡因子为-2，树失去平衡。为保证树的平衡，此时需要对节点40做出旋转，因为右子树高度高于左子树，对节点进行左旋操作，流程如下：
（1）节点的右孩子替代此节点位置
（2）右孩子的左子树变为该节点的右子树
（3）节点本身变为右孩子的左子树
图解过程：
右旋：
右旋操作与左旋类似，操作流程为：
（1）节点的左孩子代表此节点
（2）节点的左孩子的右子树变为节点的左子树
（3）将此节点作为左孩子节点的右子树。
图解过程：
