बाइनरी ट्री की गणना किसी दिए गए आकार (नोड्स की विशिष्ट संख्या) के अलग-अलग लेबल रहित बाइनरी पेड़ों की कुल संख्या की गणना कर रहा है। इस लेख में, हम n नोड्स के बाइनरी ट्री की संख्या गिनने के लिए एक प्रोग्राम बनाएंगे।
बाइनरी ट्री के नोड्स के लेबलिंग के आधार पर, यह दो प्रकार का होता है:
- लेबल बाइनरी ट्री
- बिना लेबल वाला बाइनरी ट्री
लेबल बाइनरी ट्री: यह एक बाइनरी ट्री है जिसमें एक पेड़ के नोड्स को मानों के साथ लेबल किया जाता है।
नोड्स की दी गई संख्या के लिए विभिन्न प्रकार के लेबल किए गए बाइनरी ट्री :
नोड्स की संख्या N =2
इसी तरह, हम एन नोड्स की संख्या के लिए अलग-अलग लेबल वाले बाइनरी ट्री की संख्या पा सकते हैं,
एन =1, गिनती =1
एन =2, गिनती =4
एन =3, गिनती =30
एन =4, गिनती =336
यहां, हम देख सकते हैं कि प्रत्येक लेबल वाले नोड के लिए लेबल रहित नोड्स के लिए सभी प्रकार की व्यवस्था की गई है। तो, गिनती 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 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 के लिए अलग-अलग लेबल रहित बाइनरी ट्री की संख्या ज्ञात कर सकते हैं।
एन =1, गिनती =1
एन =2, गिनती =2
एन =3, गिनती =5
एन =4, गिनती =14
इसका उपयोग करके हम एन नोड्स के लिए अलग-अलग लेबल रहित बाइनरी ट्री की संख्या तैयार कर सकते हैं,
यह कैटलन नंबर द्वारा दिया गया है,
एक अन्य सूत्र हो सकता है,
सी(एन) =(2एन!) / (एन+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