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

C++ में बाइनरी ट्री के लीफ नोड्स को पेयरवाइज़ स्वैप करना


एक बाइनरी ट्री दिया गया है। कार्य लीफ नोड्स को पेयरवाइज़ स्वैप करना है, उदाहरण के लिए -

इनपुट -

C++ में बाइनरी ट्री के लीफ नोड्स को पेयरवाइज़ स्वैप करना

आउटपुट -

C++ में बाइनरी ट्री के लीफ नोड्स को पेयरवाइज़ स्वैप करना

दिए गए समस्या में, हम दो पॉइंटर्स पर नज़र रखेंगे जो दो आसन्न लीफ नोड्स को इंगित करते हैं और उनके मानों को स्वैप करते हैं।

समाधान खोजने का दृष्टिकोण

इस दृष्टिकोण में, हम ट्री को पार करते हैं, लीफ नोड्स ढूंढते हैं, और अपने काउंटर पर नज़र रखते हैं वर्तमान गिनती चेक करने के लिए। मुख्य ट्रिक यह है कि हमारा काउंटर विषम है, इसलिए हमारा पहला पॉइंटर उस नोड को इंगित करता है अब। जब हमारा काउंटर सम हो जाता है, तो हम डेटा स्वैप करते हैं, और इस प्रकार हमारे लीफ नोड्स स्वैप हो जाते हैं।

उदाहरण

उपरोक्त दृष्टिकोण के लिए C++ कोड

 #include <bits/stdc++.h> using namespace std; struct Node{ // हमारे ट्री नोड की संरचना     int data;     struct Node *left, *right; }; void Swap(Node **a, Node **b){ // स्वैपिंग यूटिलिटी फंक्शन     Node * temp = *a;     *a = *b;     *b = temp; } /********लीफ नोड्स के लिए पॉइंटर्स स्वैपिंग के लिए********/ Node **firstleaf; Node **secondleaf; void SwapTheLeafNodes(Node **root, int &count){//लीफ नोड्स स्वैप करने के लिए //रिकर्सिव फंक्शन     if (!(*root)) // यदि रूट NULL है तो हम वापस लौटते हैं         return;     if(!(*root)->left &&!(*root)->right){ // लीफ नोड के लिए शर्त         secondleaf = root; // अब हम पहले अपने दूसरे पॉइंटर को इस नोड पर इंगित करते हैं         count++; // हम काउंट भी बढ़ाते हैं         if (count%2 == 0) // अब यदि हमारा काउंट सम है तो इसका मतलब हमारे पास एक जोड़ा है इसलिए हम उन्हें स्वैप कर सकते हैं             Swap(firstleaf, secondleaf);         else // यदि काउंट विषम है तो इसका मतलब हमें अभी केवल पहला तत्व मिला है             firstleaf = secondleaf;     }     if ((*root)->left)         SwapTheLeafNodes(&(*root)->left, count);     if ((*root)->right)         SwapTheLeafNodes(&(*root)->right, count); } Node* newNode(int data){ // नया नोड इनिशियलाइज़ करने का फंक्शन     Node *temp = new Node;     temp->data = data;     temp->left = temp->right = NULL;     return temp; } void printInorder(Node* node){ // इनऑर्डर ट्रैवर्सल फंक्शन     if (node == NULL)        return;     printInorder(node->left);     printf("%d ", node->data);     printInorder(node->right); } int main(){    /* बाइनरी ट्री बनाना*/     Node *root = newNode(1);     root->left = newNode(2);     root->right = newNode(3);     root->left->left = newNode(4);     root->right->left = newNode(5);     root->right->right = newNode(8);     root->right->left->left = newNode(6);     root->right->left->right = newNode(7);     root->right->right->left = newNode(9);     root->right->right->right = newNode(10);     cout << "Inorder traversal before swap:\n";     printInorder(root);     cout << "\n";     int count = 0; // लीफ नोड्स पर नज़र रखने के लिए हमारा काउंटर     SwapTheLeafNodes(&root, count); // नोड्स स्वैप करना     cout << "Inorder traversal after swap:\n";     printInorder(root);     cout << "\n";     return 0; }

आउटपुट

Inorder traversal before swap: 4 2 1 6 5 7 3 9 8 10 Inorder traversal after swap: 6 2 1 4 5 9 3 7 8 10

उपरोक्त कोड की व्याख्या

उपरोक्त दृष्टिकोण में, हम बस दो पॉइंटर्स बना रहे हैं जो हमारे लीफ नोड्स पर नज़र रखेंगे। हम ट्री को पार करते हैं जब हमें एक लीफ नोड मिलता है। हम पहले अपने दूसरे पॉइंटर को उस नोड पर इंगित करते हैं अब हम एक काउंट वेरिएबल बढ़ाते हैं अब यदि हमारा काउंट सम है, तो हम नोड्स को स्वैप करते हैं और यदि काउंट विषम है, तो इसका मतलब हमें केवल जोड़े का पहला तत्व मिला है, इसलिए हम उस मान को पहले पॉइंटर में स्टोर करते हैं, और इस तरह हमारा फंक्शन काम करता है।

निष्कर्ष

इस ट्यूटोरियल में, हम बाइनरी ट्री में लीफ नोड्स को पेयरवाइज़ स्वैप करने की समस्या को हल करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और पूरा दृष्टिकोण (सामान्य और कुशल) भी सीखा जिससे हमने इस समस्या को हल किया। हम यही प्रोग्राम C, Java, Python, और अन्य भाषाओं में भी लिख सकते हैं। आशा है आपको यह ट्यूटोरियल उपयोगी लगा होगा।

  1. C++ में बाइनरी ट्री में निकटतम लीफ ढूंढें C++ में बाइनरी ट्री में निकटतम लीफ ढूंढें

    मान लीजिए, एक बाइनरी ट्री दिया गया है। इसमें अलग-अलग लेवल पर लीफ नोड्स हैं। एक और पॉइंटर दिया गया है, जो एक नोड को इंगित कर रहा है। हमें इंगित नोड से निकटतम लीफ नोड की दूरी ढूंढनी है। ट्री को नीचे जैसा मानें - यहां लीफ नोड्स 2, -2 और 6 हैं। यदि पॉइंटर नोड -5 पर इंगित कर रहा है, तो -5 से निकटतम नोड

  1. C++ प्रोग्राम: बाइनरी ट्री के नोड्स को प्रिंट करना जैसे ही वे लीफ नोड बनते हैं C++ प्रोग्राम: बाइनरी ट्री के नोड्स को प्रिंट करना जैसे ही वे लीफ नोड बनते हैं

    एक बाइनरी ट्री दिया गया है, हमें उसके लीफ नोड्स को प्रिंट करना है और फिर उन लीफ नोड्स को हटाना है और फिर तब तक दोहराना है जब तक ट्री में कोई नोड न बचे। उदाहरण तो समस्या का आउटपुट होना चाहिए - 6 7 9 13 14 3 4 2 1 दृष्टिकोण हमने एक ऐसा दृष्टिकोण अपनाया है जहां हम DFS लागू कर रहे हैं। एक अस्थायी म

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

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