বাইনারি ট্রি গণনা হলো একটি নির্দিষ্ট আকারের (নির্দিষ্ট নোড সংখ্যা) স্বতন্ত্র আনলেবেলড বাইনারি ট্রির মোট সংখ্যা গণনা। এই আর্টিকেলে আমরা n নোডের বাইনারি ট্রির সংখ্যা গণনা করার প্রোগ্রাম তৈরি করব।
নোড লেবেলিংের ভিত্তিতে বাইনারি ট্রি দুই ধরনের:
- লেবেলড বাইনারি ট্রি
- আনলেবেলড বাইনারি ট্রি
লেবেলড বাইনারি ট্রি: এটি একটি বাইনারি ট্রি যেখানে ট্রির নোডগুলো মান দিয়ে লেবেল করা থাকে।
নির্দিষ্ট নোড সংখ্যার জন্য ভিন্ন লেবেলড বাইনারি ট্রির ধরন:
নোড সংখ্যা N = 2
এভাবেই, N সংখ্যক নোডের জন্য স্বতন্ত্র লেবেলড বাইনারি ট্রির সংখ্যা বের করা যায়,
N = 1, গণনা = ১
N = 2, গণনা = ৪
N = 3, গণনা = ৩০
N = 4, গণনা = ৩৩৬
এখানে, আমরা দেখতে পাই লেবেলড নোডের জন্য আনলেবেলড নোডের সব অরেঞ্জমেন্ট করা হয়। তাই গণনা হবে 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
স্বতন্ত্র আনলেবেলড বাইনারি ট্রির সংখ্যা = ২
এভাবেই, N-এর জন্য স্বতন্ত্র আনলেবেলড বাইনারি ট্রির সংখ্যা বের করা যায়।
N = 1, গণনা = ১
N = 2, গণনা = ২
N = 3, গণনা = ৫
N = 4, গণনা = ১৪
এটি ক্যাটালান নম্বর দ্বারা দেওয়া হয়,
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
