इस समस्या में हमें एक बाइनरी ट्री दिया जाता है। हमारा काम किसी दिए गए पेड़ की अधिकतम गहराई या ऊंचाई का पता लगाने के लिए एक प्रोग्राम लिखना है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
पेड़ की ऊंचाई 3 होती है।
एक पेड़ की अधिकतम ऊँचाई ज्ञात करने के लिए, हम उसके बाएँ और दाएँ उपप्रकार की ऊँचाई की जाँच करेंगे और दोनों के अधिकतम में एक जोड़ देंगे। यह एक पुनरावर्ती प्रक्रिया है जो इसे जारी रखेगी पेड़ का अंतिम नोड पाया जाता है और उप-पेड़ों की ऊंचाई खोजने के लिए उत्तरोत्तर जोड़ा जाता है।
उपरोक्त उदाहरण इस विधि का उपयोग करके हल किया गया।
पेड़ की ऊँचाई ज्ञात करना अर्थात ऊँचाई(3) =अधिकतम(ऊँचाई(5),ऊँचाई(7)) + 1.
इसके लिए, हम 5 और 7 मान वाले नोड्स की ऊंचाई की गणना करेंगे।
ऊंचाई(5) =अधिकतम(ऊंचाई(1),ऊंचाई(9)) + 1 और
ऊंचाई (7) =1, इसका कोई उप-वृक्ष नहीं है जिसे बनाया जा सकता है।
इसी तरह, ऊंचाई(1) =ऊंचाई(9) =1
ऊंचाई(5) =अधिकतम(1,1) +1 =2
ऊंचाई(3) =अधिकतम(ऊंचाई(5),ऊंचाई(7)) + 1 =अधिकतम(2,1) + 1 =3.
तो ऊंचाई 3 हो जाती है।
समाधान का वर्णन करने के लिए कार्यक्रम,
उदाहरण
#include <iostream>
using namespace std;
class node {
public:
int data;
node* left;
node* right;
};
int height(node* node) {
if (node == NULL)
return 0;
else {
int lDepth = height(node->left);
int rDepth = height(node->right);
if (lDepth > rDepth)
return(lDepth + 1);
else return(rDepth + 1);
}
}
node* insertNode(int data) {
node* Node = new node();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
return(Node);
}
int main() {
node *root = insertNode(4);
root->left = insertNode(5);
root->right = insertNode(0);
root->left->left = insertNode(1);
root->left->right = insertNode(9);
cout<<"The height of the given binary tree is "<<height(root);
return 0;
} आउटपुट
The height of the given binary tree is 3