हमें बाइनरी ट्री की ऊंचाई H दी गई है। लक्ष्य दी गई ऊंचाई के संतुलित बाइनरी ट्री की संख्या/गणना ज्ञात करना है।
एक बाइनरी ट्री - एक ट्री डेटा संरचना है जिसमें प्रत्येक नोड के अधिकतम दो बच्चे होते हैं, जो बाएं बच्चे और दाएं बच्चे होते हैं।
ऊंचाई-संतुलित बाइनरी ट्री - एक बाइनरी ट्री के रूप में परिभाषित किया गया है जिसमें हर नोड के दो उपट्री की गहराई केवल 1 या 0 से भिन्न होती है। यानी हर नोड पर बाएं उपट्री और दाएं उपट्री की ऊंचाई में अधिकतम अंतर 1 होता है।
निम्न आकृति में ऊंचाई h=3 के लिए संभावित ऊंचाई संतुलित बाइनरी ट्री हैं।
इनपुट
ऊंचाई H=2
आउटपुट
ऊंचाई H के संतुलित बाइनरी ट्री की संख्या: 3
व्याख्या - दी गई आकृति में ऊंचाई H=2 के लिए संभावित संतुलित ट्री हैं
इनपुट
ऊंचाई H=3
आउटपुट
ऊंचाई H के संतुलित बाइनरी ट्री की संख्या: 15
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण इस प्रकार है
पूर्णांक H बाइनरी ट्री की ऊंचाई को दर्शाता है।
फ़ंक्शन countBTheight(int h) ट्री की ऊंचाई को इनपुट के रूप में लेता है और ऊंचाई h के साथ संभावित संतुलित बाइनरी ट्री की संख्या लौटाता है।
हम पुनरावर्ती दृष्टिकोण का उपयोग कर रहे हैं।
यदि ट्री की ऊंचाई 1 है, यानी इसमें केवल एक नोड है तो केवल एक नोड वाला एक ट्री मौजूद है और वह संतुलित है। (if(h==1), return 1)
अन्यथा ऊंचाई बाएं और दाएं उपट्री का योग है जिनकी ऊंचाई रूट से एक या दो कम है। (संतुलित ट्री में ऊंचाई का अंतर 1 होता है)।
फ़ंक्शन परिणाम के रूप में गणना लौटाता है।
उदाहरण
#include <iostream> int countBTheight(int h){ // ऊंचाई 0 या 1 के साथ एक ट्री संभव है if (h == 0 || h == 1) return 1; return countBTheight(h-1) * (2 *countBTheight(h-2) + countBTheight(h-1)); } int main(){ int H = 4; std::cout << "ऊंचाई H के संतुलित बाइनरी ट्री की संख्या: "<<countBTheight(H); }
आउटपुट
ऊंचाई H के संतुलित बाइनरी ट्री की संख्या: 315
