Cây nhị phân cân bằng trong Python

Trong một cây nhị phân, mỗi nút chứa hai nút con, tức là nút con trái và nút con phải. Giả sử chúng ta có một cây nhị phân và cần kiểm tra xem cây đó có cân bằng hay không. Một cây nhị phân được gọi là cân bằng nếu độ chênh lệch chiều cao của cây con trái và cây con phải nhỏ hơn hoặc bằng 1.

Ví dụ

Đầu vào 1:

Đầu ra:

True

Giải thích:

Cây nhị phân cho trước là [1,2,3, NULL, NULL, 6, 7]. Độ chênh lệch chiều cao giữa cây con trái và cây con phải bằng 1, do đó đây là một cây cân bằng theo chiều cao.

Đầu vào 2:

Đầu ra:

False

Giải thích:

Cây nhị phân cho trước là [1,2,3,4, NULL, NULL, NULL, 5]. Độ chênh lệch chiều cao giữa cây con trái và cây con phải lớn hơn 1, do đó đây không phải là một cây cân bằng theo chiều cao.

Phương pháp giải quyết

Phương pháp đệ quy để giải quyết bài toán này là tìm chiều cao của cây con trái và cây con phải, sau đó kiểm tra nếu |chiều cao(cây con trái) - chiều cao(cây con phải)| ≤ 1 thì trả về True. Sau đó, chúng ta kiểm tra đệ quy cho từng nút của cây nhị phân.

• Nhập các nút của cây nhị phân.
• Định nghĩa hàm tìm chiều cao của cây.
• Một hàm Boolean để kiểm tra đệ quy nếu độ chênh lệch chiều cao của cây con trái và cây con phải không quá 1, thì trả về True.
• Trả về kết quả.

Ví dụ mã

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = self.right = None

# Lớp hỗ trợ để lưu trữ chiều cao
class Height:
    def __init__(self):
        self.height = 0

# Hàm kiểm tra cây có cân bằng hay không
def isBalanced(root):
    lh = Height()
    rh = Height()
    if root is None:
        return True
    return (
        (abs(lh.height - rh.height) <= 1)
        and isBalanced(root.left)
        and isBalanced(root.right)
    )

# Tạo cây ví dụ
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = None
root.left.right = None
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

if isBalanced(root):
    print("Cân bằng")
else:
    print("Không cân bằng")

Đầu ra

Cân bằng

Cây nhị phân cho trước [1, 2, 3, NULL, NULL, 6, 7]. Độ chênh lệch chiều cao giữa cây con trái và cây con phải bằng 1, do đó đây là một cây cân bằng theo chiều cao.