ตรวจสอบ Binary Tree เป็น Heap ใน Python

ภาพรวม

โจทย์ตรวจสอบว่า Binary Tree เป็น Heap หรือไม่ เงื่อนไข 2 ข้อ:

1. Complete Binary Tree: ทุกระดับเต็ม ยกเว้นระดับสุดท้ายที่เต็มซ้าย
2. Heap Property (Max-Heap): โหนดแม่ ≥ โหนดลูก ทุกคู่

โค้ด Python

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

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

การทำงาน

1. number_of_nodes: นับโหนดทั้งหมด (สำหรับ complete check)
2. has_heap_property: DFS เช็ค parent ≥ children
3. is_complete_tree: ใช้ index array representation เช็ค index < node_count

ผลลัพธ์

True