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

广告位

python实现二叉排序树中找出第一个大于中间值的结点 题目描述: 对于一棵二叉排序树 , 令 f=(最大值+…

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

题目描述:
对于一棵二叉排序树 , 令 f=(最大值+最小值)/2, 设计一个算法,找出距离 f值最近、大
于 f值的结点 。例如,下图所给定的二叉排序树中, 最大值为 7, 最小值为 l, 因此, f=(1+7)/2=4’ 那么在这棵二叉树中,距离结点 4最近并且大于 4 的结点为 5。
python实现二叉排序树中找出第一个大于中间值的结点

分析与解答:
首先需要找出二叉排序树中的最大值与最小值。由于二叉排序树的特点是:对于任意一 个结点,它的左子树上所有结点的值都小于这个结点的值, 它的右子树上所有结点的值都大 于这个结点的值。因此, 在二叉排序树中,最小值一定是最左下的结点,最大值一定是最右 下的结点。 根据最大值与最小值很容易就可以求出 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 if __name__=='__main__':     arr=[1,2,3,4,5,6,7]     root=arraytotree(arr,0,len(arr)-1)     print(getNode(root).data) 

输出:5

剪烛西窗, 程

关于作者: 剪烛西窗

为您推荐