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

Question

我需要为一个最小堆二进制树编写一个递归来检查这个树是否是最小堆。其中一个测试用例就是“无”。

是否将None视为最小堆树并返回True，或者None为False

我询问的原因是，我将在某个时刻到达叶子，它们的节点是None，如果基例是True，那么它将返回True。

Answer 1

我相信none类型将是空的，因为它不违反min-heap树的定义。

Answer 2

是的，没有一个被认为是均值堆树。

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)

但这取决于你想要如何处理它。任何没有子节点的节点都是min-heap或max-heap，但它没有任何意义。如果你想打电话给

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