C++ 이진 트리 열거: 레이블·비레이블 이진 트리 개수 구하기

이진 트리 열거(Binary Tree Enumeration)는 주어진 크기(특정 노드 수)로 만들 수 있는 서로 다른 이진 트리의 총 개수를 세는 작업입니다. 이 글에서는 n개의 노드로 만들 수 있는 이진 트리의 개수를 구하는 프로그램을 C++로 작성해 보겠습니다.

노드 레이블링에 따른 두 가지 유형

• 레이블 이진 트리(Labeled Binary Tree)
• 비레이블 이진 트리(Unlabeled Binary Tree)

레이블 이진 트리(Labeled Binary Tree)

레이블 이진 트리는 트리의 각 노드에 고유한 값이 붙어 있는 이진 트리입니다. 노드 값이 서로 다르기 때문에 트리의 구조가 같더라도 값의 배치가 달라지면 별개의 트리로 계산됩니다.

노드 수별 레이블 이진 트리의 개수

노드 수 N = 2일 때 서로 다른 레이블 이진 트리는 4가지입니다.

같은 방식으로 N개의 노드에 대한 레이블 이진 트리의 개수를 구할 수 있습니다.

N = 1 → 개수 1
N = 2 → 개수 4
N = 3 → 개수 30
N = 4 → 개수 336

레이블된 각 노드에 대해 비레이블 트리에서 가능한 모든 배치가 적용되므로, 전체 개수는 n! × 비레이블 이진 트리의 개수가 됩니다.

C(N) = n! × ( (2n)! / ( (n+1)! × n! ) )

레이블 이진 트리 개수를 구하는 C++ 프로그램

예제

#include <iostream>
using namespace std;

long long fact(int n){
    if(n <= 1)
        return 1;
    return n * fact(n - 1);
}

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

int main(){
    int N = 6;
    cout << "노드 " << N << "개로 만들 수 있는 서로 다른 레이블 이진 트리의 개수: "
         << distinctCountLabeledTree(N);
    return 0;
}

출력 결과 −

노드 6개로 만들 수 있는 서로 다른 레이블 이진 트리의 개수: 95040

비레이블 이진 트리(Unlabeled Binary Tree)

비레이블 이진 트리는 노드에 값이 붙어 있지 않은 이진 트리입니다. 따라서 트리의 모양(구조)만 서로 다르면 별개의 트리로 계산됩니다.

노드 수별 비레이블 이진 트리의 개수

노드 수 N = 2일 때 서로 다른 비레이블 이진 트리의 개수는 2입니다.

같은 방식으로 N개의 노드에 대한 비레이블 이진 트리의 개수를 구할 수 있습니다.

N = 1 → 개수 1
N = 2 → 개수 2
N = 3 → 개수 5
N = 4 → 개수 14

이 수열은 잘 알려진 카탈란 수(Catalan Number)와 일치하며, 다음 공식으로 계산할 수 있습니다.

C(N) = (2n)! / ( (n+1)! × n! )

비레이블 이진 트리 개수를 구하는 C++ 프로그램

예제

#include <iostream>
using namespace std;

long long fact(int n){
    if(n <= 1)
        return 1;
    return n * fact(n - 1);
}

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

int main(){
    int N = 7;
    cout << "노드 " << N << "개로 만들 수 있는 서로 다른 비레이블 이진 트리의 개수: "
         << distinctCount(N);
    return 0;
}

출력 결과 −

노드 7개로 만들 수 있는 서로 다른 비레이블 이진 트리의 개수: 429

참고: N이 커지면 팩토리얼 값이 매우 빠르게 증가하기 때문에 int 대신 long long을 사용해야 오버플로우를 피하고 정확한 결과를 얻을 수 있습니다. 예를 들어 N = 7일 때 카탈란 수는 429이며, 위 코드는 이 값을 정확히 출력합니다.