说明

二叉排序树（Binary Sort Tree），又称二叉查找树，是一颗空树，或者是具有如下性质的二叉树：

下图是一颗典型的二叉排序树：

查找速度快

在线演示

有如下 无序序列：

体验放入到二叉排序树的过程

第一步：插入 8 作为根结点。

第二步：插入 3 ，与根结点 8 进行比较，发现比8小，且根结点没有左孩子，则将 3 插入到 8 的左孩子。

第三步：插入10，首先与根结点比较，发现比 8 大，则要将 10 插入根结点的右子树；根结点 8 的右子树为空，则将 10 作为 8 的右孩子。

第四步：插入 1，首先与根结点比较，比根结点小，则应插入根结点的左子树。再与根结点的左孩子 3 比较，发现比 3 还小，则应插入 3 的左孩子。

第五步：插入 6，先与根结点8比较，小于 8，向左走；再与 3 比较，大于 3，向有走，没有结点，则将6 作为3的右孩子。

第六步：插入14，先与8比较，比 8 大，向右走；再与8的右孩子10比较，比10大，向右走，没有结点，则将14作为10的右孩子。

第七步：插入4，先与8比较，发现比8小，向左走，再与3比较，比3大向右走，再与6比较，向左走且没有左孩子，将4作为6的左孩子。

第八步：插入7，先与8比较，发现比8小，向左走，再与3比较，向右走，在与6比较，继续向右走，发现6没有右孩子，则将7作为 6的右孩子插入。

第九步：插入13，先与8比较（大于）向右，再与10比较（大于）向右，再与14比较（小于）向左，发现14的左孩子为空，则将13插入到14的左孩子位置。

查找值为 13 的结点：

第一步：访问根结点 8

第二步：根据二叉排序树的左子树均比根结点小，右子树均比根结点大的性质， 13 > 8 ，因此值为13的结点可能在根结点 8 的右子树当中，我们查看根结点的右子节点 10 ：

第三步：与第二步相似， 13 > 10 ，因此查看结点 10 的右孩子 14 ：

第四步：根据二叉排序树的左子树均比根结点小，右子树均比根结点大的性质， 13 < 14 ，因此查看 14 的左孩子 13 ，发现刚好和要查找的值相等：

从根节点一直往左走，直到无路可走就可得到最小值
从根节点一直往右走，直到无路可走，就可以得到最大值

当数据，按照 顺序存放 时，如下：

存放 2、3、5、7、6、8

会退化成链表，查询效率降低，如下：

查找元素 6 或 8 时，效率降低