介绍
二叉查找树（Binary Search Tree，BST），又称二叉排序树、二叉检索树。是满足 左小右大 规则的二叉树，核心是：查找、插入、删除都可利用二分思想，效率更高。
定义
空树 或 满足以下条件：
- 若左子树非空，左子树所有结点值 < 根结点值
- 若右子树非空，右子树所有结点值 > 根结点值
- 左、右子树本身也都是二叉排序树
关键： 中序遍历 一定是 递增有序序列。
提示：无重复值（通常约定），
特点
- 左孩子小于根
- 右孩子大于根
即：左孩子<根<右孩子
- 二叉查找树的 中序遍历序列 为 从小到大排列 的序列：上图中序遍历结果：
20、48、51、56、89、112 - 值最小的结点：无左子树
- 值最大的结点：无右子树
- 每一层从左到右进行遍历的序列为从小到大排列的序列
与 满二叉树、完全二叉树的关系
- 二叉排序树，不一定是满二叉树
- 二叉排序树，不一定是完全二叉树
题1
根据序列1: {89，48，112，20，56，51}，画出二叉排序树
规则
序列第一个元素 是 二叉排序树的根节点
之后插入的结点，值 比 父节点小，就放到左侧；反之放到右侧
答案
题2
可以构造出下图所示二叉排序树时 (二叉检索树、二叉查找树)
的 关键码序列 是（ ）
A、10 13 17 19 23 27 31 40 65 91
B、23 40 91 17 19 10 31 65 27 13
C、23 19 40 27 17 13 10 91 65 31
D、27 31 40 65 91 13 10 17 23 19
分析
注意审题，不是找 中序遍历序列，所以不是 A
规则：
序列第一个元素 是 二叉排序树的根节点
之后插入的结点，值 比 父节点小，就放到左侧；反之放到右侧
所以第一个元素是 23，所以排除 D；19 比 23 小，应该放到左侧，所以 C 错
答案
B
题3
以下关于二叉排序树寸（或二叉查找树、二叉搜索树）的叙述中正确的是（）
A、对二叉排序树进行先序、中序和后序遍历，都得到结点关键字的有序序列
B、含有n个结点的二叉排序树高度为 \left \lfloor log_2n \right \rfloor + 1
C、从根到任意一个叶子结点的路径上，结点的关键字呈现有序排列的特点
D、从左到右排列同层次的结点，其关键字呈现有序排列的特点
分析
选项 A：只有中序遍历是有序的
选项 B：完全二叉树的特性，详见 软考-软件设计师：数据结构-二叉树、满二叉树、完全二叉树、非完全二叉树、单支树
选项 C：不一定
答案
D