Đếm số cây nhị phân (Enumeration of Binary Trees) trong C++

Liệt kê cây nhị phân (Enumeration of Binary Trees) là việc đếm số lượng cây nhị phân khác nhau (distinct) với n nút.

Dựa vào việc gán nhãn (label) cho nút, có 2 loại:

• Cây nhị phân có nhãn (Labeled Binary Tree): Các nút được gán nhãn riêng biệt (1..n).
• Cây nhị phân không nhãn (Unlabeled Binary Tree): Chỉ quan tâm cấu trúc hình dạng, không quan tâm giá trị nút.

1. Cây không nhãn (Unlabeled) - Số Catalan

Số cây nhị phân không nhãn khác nhau với n nút chính là Số Catalan thứ n:

C(n) = (2n)! / ((n+1)! * n!)

Giá trị đầu tiên: n=1 -> 1; n=2 -> 2; n=3 -> 5; n=4 -> 14.

2. Cây có nhãn (Labeled)

Với mỗi cấu trúc không nhãn, ta có thể gán nhãn n! cách. Do đó:

Labeled(n) = n! * C(n) = n! * (2n)! / ((n+1)! * n!) = (2n)! / (n+1)!

Giá trị: n=1 -> 1; n=2 -> 4; n=3 -> 30; n=4 -> 336.

Chương trình minh họa (Tính Số Catalan & Labeled)

#include <iostream>
#include <vector>
using namespace std;

// Tính Catalan bằng DP để tránh tràn số và nhanh hơn giai thừa lớn
long long catalanDP(int n) {
    vector<long long> cat(n+1, 0);
    cat[0] = cat[1] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < i; j++)
            cat[i] += cat[j] * cat[i-j-1];
    }
    return cat[n];
}

// Tính giai thừa (dùng cho n nhỏ)
long long fact(int n) {
    long long res = 1;
    for (int i=2; i<=n; i++) res *= i;
    return res;
}

int main() {
    int N = 7;
    cout << "So cay UNLABELED (Catalan C_" << N << "): " << catalanDP(N) << endl;
    
    // Labeled = (2N)! / (N+1)!
    // Can thuc hien tinh toan co so lon hoac dung thu vien big integer neu N lon
    // Vi du N=7: (14)! / 8! = 14*13*...*9
    long long labeled = 1;
    for (int i = N+2; i <= 2*N; i++) labeled *= i; 
    // Cong thuc: (2n)!/(n+1)! = (n+2)(n+3)...(2n)
    
    cout << "So cay LABELED (N=" << N << "): " << labeled << endl;
    return 0;
}

Đầu ra

So cay UNLABELED (Catalan C_7): 429
So cay LABELED (N=7): 17297280

Lưu ý: Code gốc dùng hàm giai thừa đệ quy dễ tràn stack và tràn số nguyên (int) rất nhanh. Phiên bản trên dùng long long và DP/nhân dãy để an toàn hơn.