C++で二分木を列挙する：ラベル付き・ラベルなしの総数の求め方

二分木の列挙（Enumeration of Binary Tree）とは、指定されたノード数（サイズ）をもつ「相異なる二分木」が全部で何通り存在するかを数える問題です。本記事では、n 個のノードから構成される二分木の総数を求めるプログラムをC++で作成します。

ラベルの有無による2つの分類

二分木は、ノードへのラベル付けの有無によって次の2種類に分けられます。

• ラベル付き二分木（Labeled Binary Tree）
• ラベルなし二分木（Unlabeled Binary Tree）

ラベル付き二分木

ラベル付き二分木とは、木を構成する各ノードに値（ラベル）が割り当てられた二分木のことです。

ノード数ごとのラベル付き二分木の総数

ノード数 N = 2 の場合、複数の形状とラベルの組み合わせが考えられます。同様の手順で、任意のノード数 N に対する相異なるラベル付き二分木の数を求められます。

• N = 1 → 1 通り
• N = 2 → 4 通り
• N = 3 → 30 通り
• N = 4 → 336 通り

ここで注目すべきは、ラベル付きの場合「どのラベルをどの位置に置くか」という組み合わせまですべて考慮される点です。つまり、ラベルなし二分木の各形状に対して、n 個のラベルの割り当て方が 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

ラベルなし二分木

ラベルなし二分木とは、ノードに値が割り当てられておらず、木の「形状」だけで区別される二分木です。

ノード数ごとのラベルなし二分木の総数

ノード数 N = 2 の場合、子が根の左に付くパターンと右に付くパターンの2通りが存在します。同様に、任意の N に対する相異なるラベルなし二分木の数は次のように求まります。

• N = 1 → 1 通り
• N = 2 → 2 通り
• N = 3 → 5 通り
• N = 4 → 14 通り

この数列はカタラン数（Catalan number）として知られており、次の式で表されます。

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

カタラン数は 1, 1, 2, 5, 14, 42, 132, 429 … と続く有名な数列で、組み合わせ論のさまざまな場面で登場します。

ラベルなし二分木を数える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

まとめ

• ラベルなし二分木の総数は、カタラン数 C(N) = (2n)! / ((n+1)! × n!) で求められる
• ラベル付き二分木の総数は、n! × カタラン数 で求められる
• ノード数が大きくなると階乗の値が急増するため、実装では long long など大きな整数型を使用するのが安全