在二叉排序树中找出第一个大于中间值的结点

【出自HW面试题】

难度系数：★★★★☆ 被考察系数：★★★☆☆

题目描述：

对于一棵二叉排序树，令f=（最大值+最小值）/2，设计一个算法，找出距离f值最近、大于f值的结点。例如，下图所给定的二叉排序树中，最大值为7，最小值为1，因此，f=（1+7）/2=4，那么在这棵二叉树中，距离结点4最近并且大于4的结点为5。

分析与解答：

首先需要找出二叉排序树中的最大值与最小值。由于二叉排序树的特点是：对于任意一个结点，它的左子树上所有结点的值都小于这个结点的值，它的右子树上所有结点的值都大于这个结点的值。因此，在二叉排序树中，最小值一定是最左下的结点，最大值一定是最右下的结点。根据最大值与最小值很容易就可以求出f的值。接下来对二叉树进行中序遍历。如果当前结点的值小于f，那么在这个结点的右子树中接着遍历，否则遍历这个结点的左子树。实现代码如下：(www.xing528.com)

程序的运行结果如下：

5

算法性能分析：

这种方法在查找最大结点与最小结点时的时间复杂度为O（h），h为二叉树的高度，对于有N个结点的二叉排序树，最大的高度为O（N），最小的高度为O（log₂^N）。同理，在查找满足条件的结点的时候，时间复杂度也是O（h）。综上所述，这种方法的时间复杂度在最好的情况下是O（log₂^N），最坏的情况下为O（N）。