特定のバイナリツリーがPythonのヒープであるかどうかを確認します

二分木があるとしましょう。ヒープかどうかを確認する必要があります。ヒープには次のプロパティがあります。ヒープはバイナリツリーになります。そのツリーは完全なツリーである必要があります（つまり、最後を除くすべてのレベルがいっぱいである必要があります）。そのツリーのすべてのノード値は、その子ノード（max-heap）以上である必要があります。

したがって、入力が次のような場合

その場合、出力はtrueになります

これを解決するには、次の手順に従います-

• 関数number_of_nodes（）を定義します。これが定着します
• rootがnullの場合、
  • 0を返す
• それ以外の場合、
  • return（1 + number_of_nodes（root.left）+ number_of_nodes（root.right））
• 関数has_heap_property（）を定義します。これが定着します
• root.leftがnullで、root.rightがnullの場合、
  • Trueを返す
• root.rightがnullの場合、
  • root.val> =root.left.val
  の場合はtrueを返します
• それ以外の場合、
  • if（root.val>=root.left.valおよびroot.val>=root.right.val、then
    • return（has_heap_property（root.left）and has_heap_property（root.right））
  • それ以外の場合、
    • Falseを返す
• 関数is_complete_tree（）を定義します。これはroot、index、node_countを取ります
• rootがnullの場合、
  • Trueを返す
• index> =node_countの場合、
  • Falseを返す
• return（is_complete_tree（root.left、2 * index + 1、node_count）and is_complete_tree（root.right、2 * index + 2、node_count））
• メインメソッドから次の手順を実行します-
• node_count：=number_of_nodes（）
• is_complete_tree（root、0、node_count）およびhas_heap_property（root）がゼロ以外の場合、
  • Trueを返す
• それ以外の場合、
  • Falseを返す

例

理解を深めるために、次の実装を見てみましょう-

class TreeNode:
   def __init__(self, value):
      self.val = value
      self.left = None
      self.right = None
   def number_of_nodes(self, root):
      if root is None:
         return 0
      else:
         return (1 + self.number_of_nodes(root.left) + self.number_of_nodes(root.right))
   def has_heap_property(self, root):
      if (root.left is None and root.right is None):
         return True
      if root.right is None:
         return root.val >= root.left.val
      else:
         if (root.val >= root.left.val and
            root.val >= root.right.val):
            return (self.has_heap_property(root.left) and self.has_heap_property(root.right))
         else:
            return False
   def is_complete_tree(self, root,index, node_count):
      if root is None:
         return True
      if index >= node_count:
         return False
      return (self.is_complete_tree(root.left, 2 * index + 1, node_count) and self.is_complete_tree(root.right, 2 * index + 2, node_count))
   def is_heap(self):
      node_count = self.number_of_nodes(self)
      if (self.is_complete_tree(self, 0, node_count) and self.has_heap_property(self)):
         return True
      else:
         return False
root = TreeNode(99)
root.left = TreeNode(46)
root.right = TreeNode(39)
root.left.left = TreeNode(14)
root.left.right = TreeNode(5)
root.right.left = TreeNode(9)
root.right.right = TreeNode(33)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(12)
print(root.is_heap())

入力

root = TreeNode(99)
root.left = TreeNode(46)
root.right = TreeNode(39)
root.left.left = TreeNode(14)
root.left.right = TreeNode(5)
root.right.left = TreeNode(9)
root.right.right = TreeNode(33)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(12)

出力

True