Kiểm tra xem một Cây nhị phân đã cho có phải là Heap trong Python hay không

Giả sử chúng ta có một cây nhị phân; chúng ta phải kiểm tra xem nó có phải là đống hay không. Heap có thuộc tính sau:Heap sẽ là một cây nhị phân Cây đó phải là một cây hoàn chỉnh (Vì vậy, tất cả các cấp ngoại trừ cuối cùng phải đầy đủ). Mọi giá trị nút của cây đó phải lớn hơn hoặc bằng nút con của nó (max-heap).

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là true

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm number_of_nodes (). Điều này sẽ bén rễ
• nếu gốc là null, thì
  • trả về 0
• nếu không,
  • return (1 + number_of_nodes (root.left) + number_of_nodes (root.right))
• Xác định một hàm has_heap_property (). Điều này sẽ bén rễ
• nếu root.left là null và root.right là null, thì
  • trả về True
• nếu root.right là null, thì
  • trả về true khi root.val> =root.left.val
• nếu không,
  • if (root.val> =root.left.val và root.val> =root.right.val, thì
    • return (has_heap_property (root.left) và has_heap_property (root.right))
  • nếu không,
    • trả về Sai
• Xác định một hàm is_complete_tree (). Điều này sẽ lấy root, index, node_count
• nếu gốc là null, thì
  • trả về True
• if index> =node_count, then
  • trả về Sai
• return (is_complete_tree (root.left, 2 * index + 1, node_count) và is_complete_tree (root.right, 2 * index + 2, node_count))
• Từ phương thức chính, hãy làm như sau -
• node_count:=number_of_nodes ()
• nếu is_complete_tree (root, 0, node_count) và has_heap_property (root) khác 0, thì
  • trả về True
• nếu không,
  • trả về Sai

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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())

Đầu vào

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)

Đầu ra

True