Liệt kê cây nhị phân trong C ++

Liệt kê cây nhị phân là đếm tổng số cây nhị phân không được gắn nhãn riêng biệt có kích thước nhất định (số lượng nút cụ thể). Trong bài này, chúng ta sẽ tạo một chương trình để đếm số Cây nhị phân của n nút.

Dựa trên việc gắn nhãn các nút của cây nhị phân, nó có hai loại:

• Cây nhị phân được gắn nhãn
• Cây nhị phân không được gắn nhãn

Cây nhị phân được gắn nhãn: Nó là một cây nhị phân trong đó các nút của cây được gắn nhãn bằng các giá trị.

Loại cây nhị phân được gắn nhãn khác nhau cho một số nút nhất định:

Số nút N =2

Tương tự, chúng ta có thể tìm thấy số lượng Cây nhị phân có nhãn riêng biệt cho N số nút,

N =1, đếm =1

N =2, đếm =4
N =3, count =30

N =4, count =336

Ở đây, chúng ta có thể thấy đối với mỗi nút được gắn nhãn, tất cả các kiểu sắp xếp cho các nút không được gắn nhãn đều được thực hiện. Vì vậy, số đếm sẽ là n! * số lượng cây nhị phân không được gắn nhãn.

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

Chương trình minh họa số lượng Cây nhị phân không được gắn nhãn riêng biệt cho một số khối N cho trước,

Ví dụ

#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;
}

Đầu ra -

The number of Distinct labeled Binary Tree is 95040

Cây nhị phân không được gắn nhãn: Nó là một cây nhị phân trong đó các nút của cây không được gắn nhãn giá trị.

Loại cây nhị phân không được gắn nhãn khác nhau cho một số nút nhất định:

Số nút N =2

Số cây nhị phân không được gắn nhãn riêng biệt =2

Tương tự, Chúng ta có thể tìm số lượng cây nhị phân không được gắn nhãn riêng biệt cho N.

N =1, đếm =1
N =2, đếm =2
N =3, đếm =5
N =4, đếm =14

Sử dụng điều này, chúng ta có thể hình thành số lượng cây nhị phân không được gắn nhãn riêng biệt cho N nút,

Nó được đưa ra bởi số Catalan,

Một công thức khác có thể là,

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

Chương trình tìm số lượng Cây nhị phân không được gắn nhãn riêng biệt cho một số nút N nhất định,

Ví dụ

#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;
}

Đầu ra -

The number of Distinct unlabeled Binary Tree is 6