C++의 이진 트리 열거

이진 트리의 열거 주어진 크기(특정 노드 수)의 레이블이 지정되지 않은 고유한 이진 트리의 총 수를 계산합니다. 이 글에서는 n 노드의 바이너리 트리 수를 세는 프로그램을 만들 것입니다.

바이너리 트리 노드의 레이블링에 따라 두 가지 유형이 있습니다.

• 레이블이 있는 이진 트리
• 레이블 없는 이진 트리

레이블이 있는 이진 트리: 트리의 노드에 값으로 레이블이 지정된 이진 트리입니다.

주어진 노드 수에 대해 레이블이 지정된 이진 트리의 다른 유형:

노드 수 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에 대해 레이블이 지정되지 않은 고유한 바이너리 트리의 수를 찾는 프로그램,

예시

#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