बाइनरी ट्री की गणना दिए गए आकार (विशिष्ट संख्या में नोड्स) के विशिष्ट अनलेबल बाइनरी ट्री की कुल संख्या गिनना है। इस लेख में, हम 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 नोड्स के लिए विशिष्ट अनलेबल्ड बाइनरी ट्री की संख्या का सूत्र बना सकते हैं,
यह कैटलन संख्या (Catalan number) द्वारा दी जाती है,
एक अन्य सूत्र हो सकता है,
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
