हमें एक बाइनरी ट्री की ऊंचाई H के साथ दिया गया है। लक्ष्य दी गई ऊंचाई के संतुलित बाइनरी ट्री की संख्या/गिनती ज्ञात करना है।
एक बाइनरी ट्री - एक ट्री डेटा संरचना है जिसमें प्रत्येक नोड में अधिकतम दो बच्चे होते हैं, जो कि बायां बच्चा और दायां बच्चा होता है।
ऊंचाई-संतुलित बाइनरी ट्री - को एक बाइनरी ट्री के रूप में परिभाषित किया गया है जिसमें प्रत्येक नोड के दो उपप्रकारों की गहराई केवल 1 या 0 से भिन्न होती है। यानी बाएं सबट्री की ऊंचाई और हर नोड पर दाएं सबट्री का अधिकतम अंतर 1 है।
निम्न आकृति में ऊंचाई h=3 के लिए संभावित ऊंचाई संतुलित बाइनरी ट्री हैं।
इनपुट
Height H=2
आउटपुट
Count of Balanced Binary Trees of Height H is : 3
स्पष्टीकरण - दी गई आकृति में H=2 की ऊंचाई के लिए संभव संतुलित पेड़ हैं
इनपुट
Height H=3
आउटपुट
Count of Balanced Binary Trees of Height H is : 15
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
-
पूर्णांक H का उपयोग बाइनरी ट्री की ऊंचाई को दर्शाने के लिए किया जाता है।
-
फ़ंक्शन countBTheight(int h) इनपुट के रूप में पेड़ की ऊंचाई लेता है और ऊंचाई h के साथ संभावित संतुलित बाइनरी पेड़ों की संख्या देता है।
-
हम पुनरावर्ती दृष्टिकोण का उपयोग कर रहे हैं।
-
यदि पेड़ की ऊंचाई 1 है, यानी इसमें केवल एक नोड है तो एक नोड वाला केवल एक पेड़ मौजूद है और वह संतुलित है। (अगर(एच==1), वापसी 1)
-
अन्यथा ऊँचाई बाएँ और दाएँ उप-वृक्षों का योग है जिनकी ऊँचाई जड़ से एक या दो कम होती है। (संतुलित पेड़ों की ऊंचाई के बीच का अंतर 1 होता है)।
-
परिणाम के रूप में फ़ंक्शन गिनती लौटाता है।
उदाहरण
#include <iostream>
int countBTheight(int h){
// One tree is possible with height 0 or 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 << "Count of balanced binary trees of height H is: "<<countBTheight(H);
} आउटपुट
Count of balanced binary trees of height H is: 315