जांचें कि क्या दिया गया बाइनरी ट्री पायथन में हीप है

मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें जांचना है कि यह ढेर है या नहीं। ढेर में निम्नलिखित गुण हैं:ढेर एक द्विआधारी वृक्ष होगा वह वृक्ष एक पूर्ण वृक्ष होना चाहिए (इसलिए अंतिम को छोड़कर सभी स्तर पूर्ण होना चाहिए)। उस पेड़ का प्रत्येक नोड मान उसके चाइल्ड नोड (अधिकतम-ढेर) से अधिक या उसके बराबर होना चाहिए।

तो, अगर इनपुट पसंद है

तब आउटपुट सही होगा

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• फ़ंक्शन को परिभाषित करें 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) and has_heap_property(root.right))
  • अन्यथा,
    • झूठी वापसी
• एक फ़ंक्शन परिभाषित करें is_complete_tree() । यह रूट, इंडेक्स, नोड_काउंट लेगा
• यदि रूट रिक्त है, तो
  • सही लौटें
• अगर इंडेक्स>=नोड_काउंट, तो
  • झूठी वापसी
• वापसी (is_complete_tree(root.left, 2 * index + 1, node_count) and is_complete_tree(root.right, 2 * index + 2, node_count))
• मुख्य विधि से निम्न कार्य करें -
• नोड_काउंट:=number_of_nodes()
• यदि is_complete_tree(root, 0, node_count) and 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