पायथन में बाइनरी ट्री के हीप होने की जांच

समस्या विवरण

एक बाइनरी ट्री दिया गया है, जांचें कि क्या यह हीप है। हीप की शर्तें:

1. कंप्लीट बाइनरी ट्री (अंतिम लेवल को छोड़कर सभी भरे हों)
2. मैक्स-हीप प्रॉपर्टी: प्रत्येक नोड का मान अपने बच्चों से ≥ हो

उदाहरण

ट्री (रूट=99, बच्चे 46,39, आदि) — आउटपुट: True

एल्गोरिदम

1. number_of_nodes(root): कुल नोड्स गिनें
2. has_heap_property(root): रिकर्सिवली जांचें कि प्रत्येक नोड ≥ बच्चे
3. is_complete_tree(root, index, node_count): इंडेक्स-आधारित जांच (कंप्लीट ट्री में इंडेक्स < node_count)
4. दोनों शर्तें पूरी हों तो 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
        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
        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)
        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)
        return (self.is_complete_tree(self, 0, node_count) and
                self.has_heap_property(self))

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

इनपुट

निर्मित ट्री (ऊपर देखें)

आउटपुट

True