python - None だけのバイナリ ツリーは最小ヒープ ツリーと見なすことができますか?

Question

このツリーが最小ヒープかどうかを確認するには、最小ヒープのバイナリ ツリーの再帰を記述する必要があります。テストケースの 1 つは NONE です。

最小ヒープ ツリーと見なされ、をNone返すかTrue、または?NoneFalse

私が尋ねている理由は、ある時点で葉に到達し、それらのノードがNoneあり、基本ケースが である場合True、それが返されるためTrueです。

Answer 1

最小ヒープ ツリーの定義に違反しないため、none 型は空虚に真になると思います。

Answer 2

最小ヒープを意味する必要があります。ツリー構造を扱っている場合、Node の子は最も一般的に None として初期化されます。その理由の 1 つは、次のように再帰を簡単にエスケープできることです。

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)

しかし、それはあなたがそれをどのように扱いたいかによって異なります。子を持たない 1 つのノードは最小ヒープまたは最大ヒープですが、意味はありません。電話したい場合

is_min_heap(None)そうするのは自由ですが、それが真実であると言いたいかどうかはあなた次第です。

Answer 3

はい、None は平均ヒープ ツリーと見なされます。