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!

প্রদত্ত সংখ্যক নোড 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