পাইথনে দেওয়া বাইনারি ট্রি হিপ কিনা চেক করুন

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

यदि इनपुट এই तरह है:

तो आउटपुट true होगा।

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

• number_of_nodes() नामक एक फंक्शन परिभाषित करें। यह root लेगा:
  • यदि root null है, तो 0 लौटाएं
  • अन्यथा, (1 + number_of_nodes(root.left) + number_of_nodes(root.right)) लौटाएं
• has_heap_property() नामक एक फंक्शन परिभाषित करें। यह root लेगा:
  • यदि root.left null है और root.right null है, तो True लौटाएं
  • यदि root.right null है, तो root.val >= root.left.val होने पर true लौटाएं
  • अन्यथा,
    • यदि (root.val >= root.left.val और root.val >= root.right.val), तो (has_heap_property(root.left) और has_heap_property(root.right)) लौटाएं
    • अन्यथा, False लौटाएं
• is_complete_tree() नामक एक फंक्शन परिभाषित करें। यह root, index, node_count लेगा:
  • यदि root null है, तो True लौटाएं
  • यदि index >= node_count, तो False लौटाएं
  • (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) शून्येतर है, तो True लौटाएं
  • अन्यथा, False लौटाएं

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

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