验证树是否是bst

Question

我有一个练习面试问题告诉我要验证一棵树是否是一个平衡的搜索树,并给出一个验证方法...我有一个类作为

Class Node:
def __init__(self, k, val):
    self.key = k
    self.value = val
    self.left = None
    self.right = None

和树的最大值和最小值的其他函数定义为

def tree_max(node):
    maxleft  = float('-inf') if not node.left  else tree_max(node.left)
    maxright = float('-inf') if not node.right else tree_max(node.right)
    return max(node.value, maxleft, maxright)

def tree_min(node):
    minleft  = float('-inf') if not node.right else tree_min(node.left)
    minright = float('-inf') if not node.left else tree_min(node.right)
    return min(node.value, minleft, minright)

我的验证方法为

def verify(node):
    if tree_max(node.left) <= node.value and node.value <= tree_min(node.right):
       if verify(node.left) and verify(node.right):
           return True
       else:
           return False
    else:
        return False

当我尝试实现验证方法时,我的问题就出现了,即使我尝试制作BST树,我似乎总是变得虚假.我的实现如下:

root= Node(10, "Hello")
root.left = Node(15, "Fifteen")
root.right= Node(30, "Thirty")

print verify(root)

root = Node(10, "Ten")
root.right = Node(20, "Twenty")
root.left = Node(5, "Five")
root.left.right = Node(15, "Fifteen")

print verify(root)

两者都给我错误...我的验证功能或我的最小/最大功能有问题...任何帮助将不胜感激.

Answer 1

我在你的代码中看到了四个错误.

1. 首先,检查空子项是否倒退tree_min.也就是说,您node.right在访问之前检查是否存在node.left,反之亦然.

2. 其次,tree.min在叶节点上调用时返回负无穷大.您需要在最小计算中使用正无穷大(负无穷大在最大版本中是正确的).

3. 第三,你有一个逻辑错误verify,因为它无条件地调用它tree_min或tree_max它自己的子节点,即使它们中的一个或两个都是None.我建议让所有函数句柄都被传递None,而不是依赖调用者来做正确的事情.这也简化min和max代码位!

4. 最后,您正在进行比较node.value,这是您为每个节点提供的字符串.我怀疑你想要比较使用node.key.将float(like float("-inf"))与字符串(如"ten")进行比较是Python 3中的一个错误,即使在合法的Python 2中,它也可能不像您期望的那样工作.

修复这些问题后,当我创建有效和无效的树时,我得到预期的结果.你的两个例子都是无效的,所以如果你用它们来测试,你总会得到一个False结果.

最后,还有一些小问题(不是错误,但仍然可以改进).Python支持链式比较,这样你就可以简化您的第一个if中陈述verify到tree_max(node.left) <= node.key <= tree_min(node.right).您可以通过连接检查and而不是嵌套其他if语句来进一步简化代码的这一部分.

这是一个适合我的代码版本(使用Python 3,虽然我认为它向后兼容Python 2):

class Node:
    def __init__(self, k, val):
        self.key = k
        self.value = val
        self.left = None
        self.right = None

def tree_max(node):
    if not node:
        return float("-inf")
    maxleft  = tree_max(node.left)
    maxright = tree_max(node.right)
    return max(node.key, maxleft, maxright)

def tree_min(node):
    if not node:
        return float("inf")
    minleft  = tree_min(node.left)
    minright = tree_min(node.right)
    return min(node.key, minleft, minright)

def verify(node):
    if not node:
        return True
    if (tree_max(node.left) <= node.key <= tree_min(node.right) and
        verify(node.left) and verify(node.right)):
        return True
    else:
        return False

root= Node(10, "Hello")
root.left = Node(5, "Five")
root.right= Node(30, "Thirty")

print(verify(root)) # prints True, since this tree is valid

root = Node(10, "Ten")
root.right = Node(20, "Twenty")
root.left = Node(5, "Five")
root.left.right = Node(15, "Fifteen")

print(verify(root)) # prints False, since 15 is to the left of 10