ตรวจสอบว่า Binary Tree ที่ระบุนั้นเป็น Heap ใน Python . หรือไม่

สมมติว่าเรามีต้นไม้ไบนารี เราต้องเช็คก่อนว่าเป็น heap หรือเปล่า ฮีปมีคุณสมบัติดังต่อไปนี้:ฮีปจะเป็นต้นไม้ไบนารี ต้นไม้นั้นควรเป็นต้นไม้ที่สมบูรณ์ (ดังนั้น ทุกระดับยกเว้นสุดท้ายควรเต็ม) ค่าโหนดทุกค่าของทรีนั้นควรมากกว่าหรือเท่ากับโหนดย่อย (max-heap)

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์จะเป็นจริง

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน number_of_nodes() สิ่งนี้จะหยั่งราก
• ถ้ารูทเป็นโมฆะ
  • คืน 0
• มิฉะนั้น
  • ผลตอบแทน(1 + number_of_nodes(root.left) + number_of_nodes(root.right))
• กำหนดฟังก์ชัน has_heap_property() สิ่งนี้จะหยั่งราก
• ถ้า root.left เป็น null และ root.right เป็น null แล้ว
  • คืนค่า True
• ถ้า root.right เป็นโมฆะ
  • คืนค่าจริงเมื่อ root.val>=root.left.val
• มิฉะนั้น
  • ถ้า (root.val>=root.left.val และ root.val>=root.right.val แล้ว
    • ส่งคืน(has_heap_property(root.left) และ has_heap_property(root.right))
  • มิฉะนั้น
    • คืนค่าเท็จ
• กำหนดฟังก์ชัน is_complete_tree() สิ่งนี้จะทำการรูท, ดัชนี, node_count
• ถ้ารูทเป็นโมฆะ
  • คืนค่า True
• ถ้าดัชนี>=node_count แล้ว
  • คืนค่าเท็จ
• 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
• มิฉะนั้น
  • คืนค่าเท็จ

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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