Viết hàm height(T) tính chiều cao của cây tìm kiếm nhị phân T.

Để tính chiều cao của cây tìm kiếm nhị phân (BST), chúng ta có thể sử dụng phương pháp đệ quy. Chiều cao của một cây BST là độ dài của đường dẫn từ nút gốc đến nút lá xa nhất. Dưới đây là cài đặt Python cho hàm height(T) để tính chiều cao của cây tìm kiếm nhị phân T.

class TreeNode:

    def __init__(self, key):

        self.left = None

        self.right = None

        self.val = key

def height(T):

    if T is None:

        return -1  # Chiều cao của một cây rỗng là -1

    else:

        # Tính chiều cao của cây con bên trái và cây con bên phải

        left_height = height(T.left)

        right_height = height(T.right)

        # Chiều cao của cây là chiều cao lớn nhất của hai cây con cộng thêm 1

        return max(left_height, right_height) + 1

Giải thích:

• Hàm height(T) sẽ tính chiều cao của cây tìm kiếm nhị phân T bằng cách sử dụng đệ quy.
• Nếu cây T là cây rỗng (None), chiều cao của cây là -1.
• Nếu cây T không rỗng, chúng ta tính chiều cao của cây con bên trái và cây con bên phải.
• Chiều cao của cây là chiều cao lớn nhất của hai cây con cộng thêm 1 (chiều cao của nút gốc).