"如何在二叉树排序树中找出第一个大于中间值的结点"（python）

题目描述：对于一个二叉树，令f=(最大值 + 最小值)/2,设计一个算法，找出距离f值最近并且大于f值的结点。

分析与解答：首先需要找出二叉树中的最大值与最小值。由于二叉排序树的特点是：对于任意一个结点，它的左子树上所有结点的值都小于这个结点的值，它的右子树所有结点的值都大于这个结点的值。因此，在二叉排序树中。最小值一定是最左下的的结点，最大值一定是最右下的结点。根据最小，最大值便可求出f值。接下来对二叉树进行中序遍历，如果当前结点的值小于f，那么在这个结点的右子树继续遍历，否则遍历这个节点的左子树。

class BiTNode:
    def __init__(self):
        self.data = None 
        self.lchild = None 
        self.rchild = None 


def getMinNode(root):
    """查找最小结点"""
    if root == None:
        return root 
    
    while root.lchild != None:
        root = root.lchild 
    return 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:
        if root.data <= mid:
            root = root.rchild
        else:
            result = root
            root =root.lchild
    return result