python - 只是 None 的二叉树可以被认为是最小堆树吗？

Question

我需要为最小堆二叉树编写递归来检查这棵树是否是最小堆。其中一个测试用例是 NONE。

被None认为是最小堆树并返回True，或者None是False？

我问的原因是我会在某个时候到达叶子并且它们的节点是None并且如果基本情况是True那么它将返回True。

Answer 1

我相信 none 类型将是空洞的，因为它不违反最小堆树的定义。

Answer 2

是的， None 被认为是平均堆树。

Answer 3

你一定是指最小堆。当我们处理任何树结构时，Node 的子节点最常被初始化为 None。原因之一是我们可以很容易地逃避递归：

def find_node(node, data):
   if root is None:
      return
   if root.data == data:
       print "Node found"
   find_node(node.left, data)
   find_node(node.right, data)



class Node(object):

    def __init__(self, data):
       self.left = None
       self.right = None
       self.data = data

在您的情况下，您想通过遍历它来检查树是否是最小堆。你会做这样的事情

def is_min_heap(root):
  #.....check here and then do
  return is_min_heap(root.left) and is_min_heap(root.right)

但这取决于你想如何处理它。任何一个没有子节点的节点都是最小堆或最大堆，但它没有意义。如果你想打电话

is_min_heap(None)那么你可以自由地这样做，但你是否想说那是真的，这取决于你。