对于给定结点的关键字集合K={4，8，2，9，1，3，6，7，5}试构造一棵二叉排序树

首先，将第一个关键字4当作根节点。接下来，依次将每个关键字插入到树中。

插入8时，由于8>4，因此插入到根节点的右子树中。现在，根节点的右子树为8。

插入2时，由于2<4，因此插入到根节点的左子树中。现在，根节点的左子树为2，右子树为8。

插入9时，由于9>4和9>8，因此插入到8的右子树中。现在，根节点的左子树为2，右子树为8，右子树的右子树为9。

插入1时，由于1<4和1<2，因此插入到2的左子树中。现在，根节点的左子树为2，左子树的左子树为1，右子树为8，右子树的右子树为9。

插入3时，由于3<4和3>2，因此插入到2的右子树中。现在，根节点的左子树为2，左子树的左子树为1，左子树的右子树为3，右子树为8，右子树的右子树为9。

插入6时，由于6>4和6<8，因此插入到8的左子树中。现在，根节点的左子树为2，左子树的左子树为1，左子树的右子树为3，右子树为8，右子树的左子树为6，右子树的右子树为9。

插入7时，由于7>4和7>8和7>6，因此插入到8的右子树中。现在，根节点的左子树为2，左子树的左子树为1，左子树的右子树为3，右子树为8，右子树的左子树为6，右子树的右子树为9，右子树的右子树的左子树为7。

插入5时，由于5>4和5<8和5>6，因此插入到6的右子树中。现在，根节点的左子树为2，左子树的左子树为1，左子树的右子树为3，右子树为8，右子树的左子树为6，右子树的右子树为9，右子树的右子树的左子树为7，右子树的左子树的左子树为5。

最终，得到的二叉排序树如下所示：

            4
           / \
          2   8
         / \ / \
        1  3 6  9
           /   / \
          5   7   None

注意，最后一个关键字5插入到了6的右子树中，而不是8的左子树中，因为6的深度比8的深度小。