Đếm cây nhị phân cân bằng chiều cao h trong C++

Cho chiều cao H của một cây nhị phân. Mục tiêu là tìm số lượng cây nhị phân cân bằng có chiều cao đã cho.

Cây nhị phân là cấu trúc dữ liệu cây mà mỗi nút có tối đa hai con: con trái và con phải.

Cây nhị phân cân bằng theo chiều cao được định nghĩa là cây nhị phân mà độ sâu của hai cây con của mọi nút chỉ khác nhau 1 hoặc 0. Tức là chiều cao cây con trái và phải tại mọi nút chênh lệch tối đa 1.

Hình sau minh họa các cây nhị phân cân bằng có thể cho h=3.

Ví dụ 1

Đầu vào: Chiều cao H = 2

Đầu ra: Số cây nhị phân cân bằng chiều cao H: 3

Giải thích: Hình vẽ chứa các cây cân bằng cho H=2.

Ví dụ 2

Đầu vào: Chiều cao H = 3

Đầu ra: Số cây nhị phân cân bằng chiều cao H: 15

Phương pháp trong chương trình

• Số nguyên H biểu diễn chiều cao cây nhị phân.
• Hàm countBTheight(int h) nhận chiều cao, trả về số cây nhị phân cân bằng có chiều cao h.
• Sử dụng phương pháp đệ quy.
• Nếu cây có chiều cao 1 (chỉ có một nút), chỉ có một cây cân bằng (if h==1 return 1).
• Ngược lại, chiều cao là tổng của cây con trái và phải với chiều cao nhỏ hơn 1 hoặc 2 so với gốc (cây cân bằng chênh lệch chiều cao tối đa 1).
• Hàm trả về số lượng.

Mã ví dụ

#include <iostream>

int countBTheight(int h) {
    // Một cây có thể với chiều cao 0 hoặc 1
    if (h == 0 || h == 1)
        return 1;
    return countBTheight(h-1) * (2 * countBTheight(h-2) + countBTheight(h-1));
}

int main() {
    int H = 4;
    std::cout << "Số cây nhị phân cân bằng chiều cao H là: " << countBTheight(H);
}

Đầu ra

Số cây nhị phân cân bằng chiều cao H là: 315