document.write('首先需要找出二叉排序树中的最大值与最小值。由于二叉排序树的特点是：对于任意一个结点，它的左
子树上所有结点的值都小于这个结点的值，它的右子树上所有结点的值都大于这个结点的值。因此，在
二叉排序树中，最小值一定是最左下的结点，最大值一定是最右下的结点。根据最大值与最小值很容易
就可以求出f的值。接下来对二叉树进行中序遍历。如果当前结点的值小于f，那么在这个结点的右子树
中接着遍历，否则遍历这个结点的左子树。实现代码如下：
class BiTNode:
def __init__(self):
self.data=None
self.lchild=None
self.rchild=None
"""
方法功能: 查找值最小的结点
输入参数: root:根结点
返回值: 值最小的结点
"""
def getMinNode(root):
if root==None:
return root
while root.lchild!=None:
root=root.lchild
return root
"""
方法功能: 查找值最大的结点
输入参数: root:根结点
返回值: 值最大的结点
"""
def getMaxNode(root):
if root==None:
return root
while root.rchild!=None:
root=root.rchild
return root
def getNode(root):
maxNode=getMaxNode(root)
minNode=getMinNode(root)
mid=(maxNode.data+minNode.data)/2
result=None
while root!=None:
#当前结点的值不大于f, 则在右子树上找
if root.data＜=mid:
root=root.rchild
#否则在左子树上找
else:
result=root
root=root.lchild
return result
if __name__=="__main__":
arr=[1,2,3,4,5,6,7]
root=arraytotree(arr,0,len(arr)-1)
print getNode(root).data
程序的运行结果为：
5
算法性能分析：
这种方法在查找最大结点与最小结点时的时间复杂度为O(h)，h为二叉树的高度，对于有N个结点的
二叉排序树，最大的高度为O(N)，最小的高度为O(log2N)。同理，在查找满足条件的结点的时候，时
间复杂度也是O(h)。综上所述，这种方法的时间复杂度在最好的情况下是O(logN)，最坏的情况下为
O(N)。
');