树（一）：二叉查找树

一、二叉查找树的定义

        二叉查找树（BST，Binary Search Tree），也称为二叉排序树或者二叉搜索树，是二叉树的一种。二叉查找树与二叉树一样，可以为空；另外，如果不为空，作为二叉查找树需满足以下性质：

        1. 非空左子树的所有键值小于其根节点的键值；

        2. 非空右子树的所有键值大于其根节点的键值；

        3. 左、右子树都是二叉查找树。

        为什么二叉查找树会具有这样的性质，因为二叉查找树的构造就是将值小的元素放到了左子树节点，值大的元素放到了右子树节点，这样可以增加查询的效率，其思想与二分查找法是一样的。

        如下图所示，就是一棵二叉查找树。

二、二叉查找树的最大元素与最小元素

        二叉查找树的最大元素一定是在树的最右端节点上，最小元素一定是在树的最左端节点上。当然，最大元素与最小元素也不一定是在叶子节点上，因为最左端的最小元素可能还有右子树，而最右端的最大元素也可能有左子树，如下图所示。

        13是最小的元素，它在最左端节点上，但是它不是叶子节点，它还有右子树，其元素为14；而30是最大的元素，它是最右端的节点，但是它不是叶子节点，它还有左子树,其元素为27。