একটি প্রদত্ত বাইনারি ট্রি পাইথনে হিপ কিনা তা পরীক্ষা করুন

ধরুন আমাদের একটি বাইনারি গাছ আছে; এটা গাদা কি না আমাদের পরীক্ষা করতে হবে। স্তূপের নিম্নলিখিত বৈশিষ্ট্য রয়েছে:হিপ একটি বাইনারি গাছ হবে যে গাছটি একটি সম্পূর্ণ গাছ হওয়া উচিত (সুতরাং শেষটি ছাড়া সমস্ত স্তর পূর্ণ হওয়া উচিত)। সেই গাছের প্রতিটি নোডের মান তার চাইল্ড নোডের (সর্বোচ্চ-হিপ) থেকে বেশি বা সমান হওয়া উচিত।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট সত্য হবে

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন সংজ্ঞায়িত করুন number_of_nodes()। এটি রুট নেবে
• যদি রুট নাল হয়, তাহলে
  • রিটার্ন 0
• অন্যথায়,
  • রিটার্ন(1 + number_of_nodes(root.left) + number_of_nodes(root.right))
• একটি ফাংশন সংজ্ঞায়িত করুন has_heap_property()। এটি রুট নেবে
• যদি root.left null হয় এবং root.right null হয়, তাহলে
  • সত্য ফেরান
• যদি 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() সংজ্ঞায়িত করুন। এটি root,index, node_count
নেবে
• যদি রুট নাল হয়, তাহলে
  • সত্য ফেরান
• যদি সূচক>=node_count, তারপর
  • মিথ্যে ফেরত দিন
• রিটার্ন(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) অ-শূন্য হয়, তাহলে
  • সত্য ফেরান
• অন্যথায়,
  • মিথ্যে ফেরত দিন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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