हमें एक बाइनरी ट्री दिया गया है। लक्ष्य दिए गए पेड़ में अधिकतम लंबाई चक्र खोजना है। हम रूटनोड से लेफ्ट सबट्री और राइट सबट्री की अधिकतम ऊंचाई का पता लगाकर ऐसा करेंगे और सबसे लंबा चक्र पाने के लिए इन अधिकतम लंबाई वाले रास्तों से जुड़ेंगे।
उपरोक्त पेड़ के लिए अधिकतम लंबाई चक्र 1-2-3-4-7-6 या 1-6-7-4-3-2-1 है। लंबाई 6 है।
इनपुट - पेड़
आउटपुट − अधिकतम लंबाई चक्र है − 5
स्पष्टीकरण - बाएँ उप-वृक्ष की अधिकतम ऊँचाई 3 और दाएँ उप-वृक्ष की ऊँचाई 1 है। चक्र की लंबाई 3+1+1=5 हो जाती है। साइकिल 1-2-3-4-6 या 1-6-4-3-2
इनपुट - पेड़
आउटपुट − अधिकतम लंबाई चक्र है − 7
स्पष्टीकरण - बाएँ सबट्री की अधिकतम ऊँचाई 3 और दाएँ सबट्री की 3 है। साइकिल की लंबाई 3+3+1=7 हो जाती है। साइकिल 5-4-2-1-8-7-6 या 5-6-7-8-1-2-4-5
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
-
एक वर्ग ट्रीनोड बनाएं जिसमें सार्वजनिक डेटा सदस्य हों - नोड के वजन के लिए इंट डेटा, ऐसे अन्य नोड्स को इंगित करने के लिए बाएं और दाएं ट्रीनोड पॉइंटर्स।
-
फ़ंक्शन newNode(int data) डेटा को एक पैरामीटर के रूप में लेता है और एक नोड बनाता है जिसमें बाएँ और दाएँ पॉइंटर्स NULL के रूप में होते हैं।
-
newnode() फ़ंक्शन को कॉल करके एक ट्री बनाएं।
-
फ़ंक्शन maxheight(treenode* root) पेड़ की जड़ लेता है और जड़ में निहित पेड़ की अधिकतम ऊंचाई लौटाता है।
-
यह फ़ंक्शन जांचता है कि क्या रूट NULL है, इसका मतलब है कि ऊंचाई 0 है, वापसी 0.
-
ऊंचाई और ऊंचाई नोड रूट के बाएं और दाएं उपट्री की ऊंचाई की गणना करती है, अधिकतम ऊंचाई (रूट-> बाएं) पर रिकर्सिव कॉल द्वारा; और maxheight(root->right);
-
ऊँचाई और ऊँचाई की तुलना करके प्राप्त अधिकतम मान लौटाएँ।
-
मेन के अंदर हम ट्रीनोड के लेफ्ट सबट्री और राइट सबट्री की अधिकतम ऊंचाई के मानों को स्टोर करते हैं।
-
अब अधिकतम लंबाई चक्र रूट को शामिल करने के लिए अधिकतम ऊंचाई +अधिकतम ऊंचाई+1 दोनों का योग है।
-
परिणामस्वरूप चक्र की लंबाई प्रिंट करें।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
//class for tree
class treenode{
public:
int data;
treenode* left;
treenode* right;
};
//find maximum height between left and right subtree of current root
int maxheight(treenode* root){
if (root == NULL)
return 0;
else{
int lheight = maxheight(root->left);
int rheight = maxheight(root->right);
//find maximum height
if (lheight > rheight)
return(lheight + 1);
else
return(rheight + 1);
}
}
//creating a node of tree
treenode* newNode(int data){
treenode* Node = new treenode();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
return(Node);
}
int main(){
treenode *root = newNode(6);
root->left = newNode(8);
root->right = newNode(9);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->left->right->right = newNode(7);
root->left->right->right->left = newNode(2);
int maxlheight=maxheight(root->left);
int maxrheight=maxheight(root->right);
int maxlheight=maxDepth(root->left);
int maxrheight=maxDepth(root->right);
cout << "Maximum length cycle: " << maxlheight+maxrheight+1;
return 0;
} आउटपुट
Maximum length cycle: 6