Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में बाइनरी ट्री के दो नोड्स को जोड़कर बनने वाले अधिकतम लंबाई के चक्र


हमें एक बाइनरी ट्री दिया गया है। लक्ष्य दिए गए ट्री में अधिकतम लंबाई का चक्र ढूंढना है। हम इसे रूट नोड से बाएं उपट्री और दाएं उपट्री की अधिकतम ऊंचाई ढूंढकर और इन अधिकतम लंबाई के पथों को जोड़कर सबसे लंबा चक्र प्राप्त करेंगे।

C++ में बाइनरी ट्री के दो नोड्स को जोड़कर बनने वाले अधिकतम लंबाई के चक्र

उपरोक्त ट्री के लिए अधिकतम लंबाई का चक्र 1-2-3-4-7-6 या 1-6-7-4-3-2-1 है। लंबाई 6 है।

इनपुट: ट्री

C++ में बाइनरी ट्री के दो नोड्स को जोड़कर बनने वाले अधिकतम लंबाई के चक्र

आउटपुट: अधिकतम लंबाई का चक्र: 5

व्याख्या: बाएं उपट्री की अधिकतम ऊंचाई 3 है और दाएं उपट्री की 1। चक्र की लंबाई 3+1+1=5 हो जाती है। चक्र है 1-2-3-4-6 या 1-6-4-3-2

इनपुट: ट्री

C++ में बाइनरी ट्री के दो नोड्स को जोड़कर बनने वाले अधिकतम लंबाई के चक्र

आउटपुट: अधिकतम लंबाई का चक्र: 7

व्याख्या: बाएं उपट्री की अधिकतम ऊंचाई 3 है और दाएं उपट्री की 3। चक्र की लंबाई 3+3+1=7 हो जाती है। चक्र है 5-4-2-1-8-7-6 या 5-6-7-8-1-2-4-5

प्रयुक्त दृष्टिकोण

  • एक क्लास treenode बनाएं जिसमें पब्लिक डेटा सदस्य हों - नोड के वजन के लिए int data, अन्य ऐसे नोड्स को इंगित करने के लिए लेफ्ट और राइट treenode पॉइंटर्स।
  • फ़ंक्शन newNode(int data) डेटा को पैरामीटर के रूप में लेता है और लेफ्ट और राइट पॉइंटर्स को NULL के साथ एक नोड बनाता है।
  • newnode() फ़ंक्शन को कॉल करके एक ट्री बनाएं।
  • फ़ंक्शन maxheight(treenode* root) ट्री के रूट को लेता है और रूट पर रूटेड ट्री की अधिकतम ऊंचाई लौटाता है।
  • यह फ़ंक्शन जांचता है कि रूट NULL है, मतलब ऊंचाई 0 है, 0 लौटाएं।
  • lheight और rheight नोड रूट के बाएं और दाएं उपट्री की ऊंचाई की गणना करते हैं, maxheight(root->left); और maxheight(root->right); के रिकर्सिव कॉल द्वारा।
  • lheight और rheight की तुलना करके प्राप्त अधिकतम मान लौटाएं।
  • मुख्य फ़ंक्शन के अंदर हम ट्री नोड के बाएं उपट्री और दाएं उपट्री की अधिकतम ऊंचाई के मान संग्रहीत करते हैं।
  • अब अधिकतम लंबाई का चक्र दोनों maxlheight + maxrheight + 1 का योग है जिसमें रूट स्वयं शामिल है।
  • चक्र की लंबाई को परिणाम के रूप में प्रिंट करें।

उदाहरण कोड

#include <bits/stdc++.h> using namespace std; //ट्री के लिए क्लास class treenode{ public: int data; treenode* left; treenode* right; }; //वर्तमान रूट के बाएं और दाएं उपट्री के बीच अधिकतम ऊंचाई ढूंढें int maxheight(treenode* root){ if (root == NULL) return 0; else{ int lheight = maxheight(root->left); int rheight = maxheight(root->right); //अधिकतम ऊंचाई ढूंढें if (lheight > rheight) return(lheight + 1); else return(rheight + 1); } } //ट्री का नोड बनाना 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 << "अधिकतम लंबाई का चक्र: " << maxlheight+maxrheight+1; return 0; }

आउटपुट

अधिकतम लंबाई का चक्र: 6

  1. C++ में बाइनरी ट्री के सभी लीफ नोड्स को दाएं से बाएं प्रिंट करना C++ में बाइनरी ट्री के सभी लीफ नोड्स को दाएं से बाएं प्रिंट करना

    इस समस्या में, हमें एक बाइनरी ट्री दी गई है और हमें बाइनरी ट्री के सभी लीफ नोड्स को दाएं से बाएं प्रिंट करना है। उदाहरण इनपुट - आउटपुट - 7 4 1 इस समस्या को हल करने के लिए, हमें बाइनरी ट्री को पार करना होगा। यह ट्रैवर्सल दो तरीकों से किया जा सकता है - प्रीऑर्डर ट्रैवर्सल यह ट्रैवर्सल रिकर्सन का

  1. बाइनरी ट्री के दो नोड्स के बीच की दूरी खोजें C++ में बाइनरी ट्री के दो नोड्स के बीच की दूरी खोजें C++ में

    मान लीजिए हमारे पास कुछ नोड्स के साथ एक बाइनरी ट्री है। हमें दो नोड्स u और v के बीच की दूरी खोजनी है। मान लीजिए ट्री नीचे जैसा है - अब (4, 6) के बीच की दूरी = 4, पथ की लंबाई 4 है, (5, 8) के बीच की लंबाई = 5 आदि। इस समस्या को हल करने के लिए, हम LCA (निम्नतम सामान्य पूर्वज) खोजेंगे, फिर LCA से दो नोड

  1. C++ प्रोग्राम: बाइनरी ट्री में लीफ नोड्स को बाएं से दाएं एक स्टैक का उपयोग करके प्रिंट करना C++ प्रोग्राम: बाइनरी ट्री में लीफ नोड्स को बाएं से दाएं एक स्टैक का उपयोग करके प्रिंट करना

    प्रोग्राम को बाइनरी ट्री के लीफ नोड्स को बाएं से दाएं प्रिंट करना चाहिए लेकिन चुनौती केवल एक स्टैक का उपयोग करना है। push() फ़ंक्शन के माध्यम से बाइनरी ट्री के नोड्स डालें और pop() ऑपरेशन के माध्यम से लीफ नोड्स प्रदर्शित करें। लीफ नोड्स अंतिम नोड्स हैं जिनका बाएं और दाएं पॉइंटर NULL होता है जिसका अर