주어진 이진 트리가 Python에서 힙인지 확인하십시오.

이진 트리가 있다고 가정합니다. 힙인지 아닌지 확인해야 합니다. 힙에는 다음과 같은 속성이 있습니다. 힙은 이진 트리가 됩니다. 해당 트리는 완전한 트리여야 합니다(그래서 마지막을 제외한 모든 수준은 가득 차 있어야 함). 해당 트리의 모든 노드 값은 자식 노드(최대 힙)보다 크거나 같아야 합니다.

따라서 입력이 다음과 같으면

그러면 출력이 true가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• number_of_nodes() 함수를 정의합니다. 이것은 뿌리를 내릴 것입니다
• 루트가 null이면
  • 0을 반환
• 그렇지 않으면
  • return(1 + number_of_nodes(root.left) + number_of_nodes(root.right))
• has_heap_property() 함수를 정의합니다. 이것은 뿌리를 내릴 것입니다
• root.left가 null이고 root.right가 null이면
  • 참 반환
• 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) 및 has_heap_property(root.right))
  • 그렇지 않으면
    • 거짓을 반환
• is_complete_tree() 함수를 정의합니다. 이것은 root,index, node_count
를 취합니다.
• 루트가 null이면
  • 참 반환
• 인덱스>=node_count인 경우
  • 거짓을 반환
• return(is_complete_tree(root.left, 2 * index + 1, node_count) 및 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)가 0이 아니면
  • 참 반환
• 그렇지 않으면
  • 거짓을 반환

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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