前言

数据结构中，线性表分为无序线性表和有序线性表。
无序线性表的数据是杂乱无序的，所以在插入和删除时，没有什么必须遵守的规则，可以插入在数据尾部或者删除在数据尾部。但是在查找的时候，需要遍历整个数据表，导致无序线性表的查找效率低。
有序线性表的数据则相反，查找数据时的时候因为数据是有序的，可以用二分法、插值法、斐波那契查找法来实现。但是，当进行插入和删除操作时，需要维护表中数据的有序性，会耗费大量的时间。
那么，我们希望找到一种数据结构，既可以有较高的插入和删除效率，并且具备较高的查找效率，因此，二叉排序树应运而生。

定义
二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），也称二叉搜索树。二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树；

构造一棵二叉排序树
现有序列：61 87 59 47 35 73 51 98 37 93

构造过程如下：
1）索引 i = 0，A[i] = 61，结点61作为根结点，如图：

2）索引 i = 1，A[1] = 87, 87 > 61，且结点61右孩子为空，故81为61结点的右孩子，如图：

3）索引 i = 2，A[i] = 59，59 < 61，且结点61左孩子为空，故59为61结点的左孩子，如图：

4）索引 i = 3，A[3] = 47，47 < 59，且结点59左孩子为空，故47为59结点的左孩子，如图：

5）索引 i = 4，A[4] = 35，35 < 47，且结点47左孩子为空，故35为47结点的左孩子，如图：

采用同样规则遍历整个数组得到如图所示的一棵排序二叉树。

二叉排序树查找
由二叉树的递归定义性质，二叉排序树的查找同样可以使用如下递归算法查找。

如果树是空的，则查找结束，无匹配。
如果被查找的值和根结点的值相等，查找成功。否则就在子树中继续查找。如果被查找的值小于根结点的值就选择左子树，大于根结点的值就选择右子树。

在理想情况下，每次比较过后，树会被砍掉一半，近乎折半查找。
遍历打印可以使用中序遍历，打印出来的结果是从小到大的有序数组。
查找代码：

typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */ 

/* 二叉树的二叉链表结点结构定义 */
typedef  struct BiTNode /* 结点结构 */
{
    int data;   /* 结点数据 */
    struct BiTNode *lchild, *rchild;    /* 左右孩子指针 */
} BiTNode, *BiTree;


/* 递归查找二叉排序树T中是否存在key, */
/* 指针f指向T的双亲，其初始调用值为NULL */
/* 若查找成功，则指针p指向该数据元素结点，并返回TRUE */
/* 否则指针p指向查找路径上访问...

课后习题

【2018年真题】已知二叉排序树如下图所示，元素之间应满足的大小关系是（）

A. x1 < x2 < x5        B. x1 < x4 < x5        C. x3 < x5 < x4        D. x4 < x3 < x5

参考答案：C

【2013年真题】在任意一棵非空二叉排序树T1中，删除某结点v 之后形成二叉排序树T2，再将v插入T2形成二叉排序树T3。下列关于T1与T3的叙述中，正确的是（）
I. 若v 是 T1 的叶结点，则 T1 与 T3 不同 
II.若v 是 T1 的叶结点，则 T1 与 T3 相同 
III. 若v 不是 T1 的叶结点，则 T1 与 T3 不同 
IV. 若v 不是 T1 的叶结点，则 T1 与 T3 相同 
A. 仅 I、III         B. 仅 I、IV         C. 仅 II、III         D. 仅 II、IV

参考答案：C
答案解析：在一棵二叉排序树中删除一个结点后再将此结点插入到二叉排序树中，如果删除的结 点是叶子结点，那么在插入结点后，后来的二叉排序树与删除结点之前相同。如果删除的结 点不是叶子结点，那么再插入这个结点后，后来的二叉树可能发生变化，不完全相同。 

【2011年真题】对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（）。
A．95,22,91,24,94,71
B．92,20,91,34,88,35 
C．21,89,77,29,36,38 
D．12,25,71,68,33,34

解答：A。选项A中，当查到91后再向24查找，说明这一条路径之后查找的数都要比91小，后面的94就错了。 

【2009年真题】下列二叉排序树中，满足平衡二叉树定义的是（）。 

参考答案：B
答案解析：考查平衡二叉树的定义。 
根据平衡二叉树的定义有，任意结点的左右子树高度差的绝对值不超过 1。而其余三个答案均可以找到不符合的结点。