Kiểm tra cây nhị phân có phải Heap trong Python

Cho cây nhị phân, kiểm tra xem nó có phải max-heap không. Điều kiện: (1) cây hoàn chỉnh (complete), (2) giá trị nút cha ≥ giá trị nút con.

Ví dụ: cây với gốc 99, các nút con 46,39,14,5,9,33,7,12 → True.

Thuật toán

• number_of_nodes(root): đếm tổng nút
• has_heap_property(root): kiểm tra đệ quy cha ≥ con
• is_complete_tree(root, index, node_count): kiểm tra tính hoàn chỉnh bằng chỉ số mảng
• Kết hợp cả hai điều kiện

Ví dụ mã 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)

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

Đầu vào

Cây nhị phân với gốc 99 và các nút con như mã

Đầu ra

True