C++での二分木の列挙

二分木の列挙 は、指定されたサイズ（特定のノード数）の個別のラベルなし二分木の総数をカウントしています。この記事では、nノードの二分木の数を数えるプログラムを作成します。

二分木のノードのラベル付けに基づいて、2つのタイプがあります：

• ラベル付き二分木
• ラベルのない二分木

ラベル付き二分木： これは、ツリーのノードに値のラベルが付けられた二分木です。

特定の数のノードに対するさまざまなタイプのラベル付き二分木：

ノード数N=2

同様に、N個のノードに対して個別にラベル付けされた二分木の数を見つけることができます

N =1、カウント=1

N =2、カウント=4
N =3、カウント=30

N =4、カウント=336

ここでは、ラベル付けされたノードごとに、ラベル付けされていないノードに対して行われたすべてのタイプの配置が行われていることがわかります。したがって、カウントはnになります！ *ラベルのない二分木の数。

C（N）=n！ *（（2n！）/（n + 1）！* n！））

特定の数のノーブNに対する個別のラベルなし二分木の数を示すプログラム

例

#include <iostream>
using namespace std;

int fact(int n){
   if(n == 1)
      return 1;
   return 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<<"The number of Distinct labeled Binary Tree is "<<distinctCountLabeledTree(N);
   return 0;
}

出力-

The number of Distinct labeled Binary Tree is 95040

ラベルのない二分木： これは、ツリーのノードに値のラベルが付けられていない二分木です。

特定の数のノードに対するさまざまなタイプのラベルなし二分木：

ノード数N=2

個別のラベルのない二分木の数=2

同様に、Nの個別のラベルなし二分木の数を見つけることができます。

N =1、カウント=1
N =2、カウント=2
N =3、カウント=5
N =4、カウント=14

これを使用して、Nノードの個別のラベルなし二分木の数を定式化できます。

カタラン数で与えられます

別の式は次のようになります。

C（N）=（2n！）/（n + 1）！ * n！

指定されたノード数Nの個別のラベルなし二分木の数を見つけるプログラム

例

#include <iostream>
using namespace std;

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

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

int main(){
   
   int N = 7;
   cout<<"The number of Distinct unlabeled Binary Tree is "<<distinctCount(N);
   return 0;
}

出力-

The number of Distinct unlabeled Binary Tree is 6