การนับจำนวนต้นไม้แบบทวิภาค (Enumeration of Binary Trees) ใน C++

บทนำ

Enumeration of Binary Tree คือการนับจำนวนต้นไม้แบบทวิภาคที่แตกต่างกัน (Distinct) และไม่มีฉลาก (Unlabeled) ที่มีจำนวนโหนดเท่ากัน

สองประเภทของต้นไม้แบบทวิภาค

• Labeled Binary Tree: โหนดมีฉลากค่า
• Unlabeled Binary Tree: โหนดไม่มีฉลาก

จำนวนต้นไม้ Labeled

N=1: 1, N=2: 4, N=3: 30, N=4: 336

สูตร: C(N) = N! × Catalan(N) = N! × (2N)! / ((N+1)! N!)

โปรแกรมนับ Labeled Binary Tree

#include <iostream>
using namespace std;

int fact(int n) { return (n <= 1) ? 1 : n * fact(n-1); }

int distinctCountLabeledTree(int N) {
    return fact(N) * (fact(2*N) / (fact(N+1) * fact(N)));
}

int main() {
    int N = 6;
    cout << "Distinct labeled Binary Trees: " << distinctCountLabeledTree(N);
    return 0;
}

ผลลัพธ์: 95040

จำนวนต้นไม้ Unlabeled (Catalan Numbers)

N=1: 1, N=2: 2, N=3: 5, N=4: 14

สูตร: C(N) = (2N)! / ((N+1)! N!)

โปรแกรมนับ Unlabeled Binary Tree

#include <iostream>
using namespace std;

int fact(int n) { return (n <= 1) ? 1 : n * fact(n-1); }

int distinctCount(int N) {
    return fact(2*N) / (fact(N+1) * fact(N));
}

int main() {
    int N = 7;
    cout << "Distinct unlabeled Binary Trees: " << distinctCount(N);
    return 0;
}

ผลลัพธ์: 429 (สำหรับ N=7)