算法与数据结构(3): 二叉搜索树

二叉搜索树（binary search tree, BST）又被称之为二叉排序树，其是一棵空二叉树或具有如下性质的二叉树：

• 若它的左子树不为空，则左子树上的所有结点的关键字（key）的值都小于根节点的关键字的值。
• 若它的右子树不为空，则右子树上的所有结点的关键字的值都大于（或等于）根节点的关键字的值。
• 它的左子树和右子树也是二叉搜索树。

下图为二叉搜索树的示例：

重要性质：中序遍历二叉搜索树获取的结点关键字序列是递增有序的。