एक बाइनरी ट्री दिया। कार्य लीफ नोड्स को जोड़ीदार स्वैप करना है, उदाहरण के लिए -
इनपुट -
आउटपुट -
हम दो पॉइंटर्स का ट्रैक रखेंगे जो दो आसन्न लीफ नोड्स को इंगित करते हैं और दी गई समस्या में उनके मूल्यों को स्वैप करते हैं।
समाधान खोजने के लिए दृष्टिकोण
इस दृष्टिकोण में, हम पेड़ को पार करते हैं, लीफ नोड्स ढूंढते हैं, और वर्तमान गिनती की जांच के लिए अपने काउंटर का ट्रैक रखते हैं। मुख्य चाल यह है कि हमारा काउंटर विषम है, इसलिए हमारा पहला पॉइंटर अब उस नोड की ओर इशारा करता है। जब हमारा काउंटर सम हो जाता है, तो हम डेटा को स्वैप करते हैं, और इसलिए हमारे लीफ नोड्स को स्वैप किया जाता है।
उदाहरण
उपरोक्त दृष्टिकोण के लिए C++ कोड
#include <bits/stdc++.h>
using namespace std;
struct Node{ // structure of our tree node
int data;
struct Node *left, *right;
};
void Swap(Node **a, Node **b){ // the swapping utility function
Node * temp = *a;
*a = *b;
*b = temp;
}
/********Pointers for leaf nodes for swapping********/
Node **firstleaf;
Node **secondleaf;
void SwapTheLeafNodes(Node **root, int &count){//recursive function for
//Swapping leaf nodes
if (!(*root)) // if root is null we return
return;
if(!(*root)->left &&!(*root)->right){ // condition for leaf node
secondleaf = root; // now we firstly make our second pointer point to this node
count++; // we also increment the count
if (count%2 == 0) // now if our count is even that means we have a pair so we can swap them
Swap(firstleaf, secondleaf);
else // if count is odd so that means we only got first node yet
firstleaf = secondleaf;
}
if ((*root)->left)
SwapTheLeafNodes(&(*root)->left, count);
if ((*root)->right)
SwapTheLeafNodes(&(*root)->right, count);
}
Node* newNode(int data){ // function for initializing new node
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
void printInorder(Node* node){ // inorder traversal function
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}
int main(){
/* Creating binary tree*/
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; // out counter for keeping track of leaf nodes
SwapTheLeafNodes(&root, count); // swapping the nodes
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++ प्रोग्राम और संपूर्ण दृष्टिकोण (सामान्य और कुशल) भी सीखा जिसके द्वारा हमने इस समस्या को हल किया। हम उसी प्रोग्राम को अन्य भाषाओं जैसे सी, जावा, पायथन और अन्य भाषाओं में लिख सकते हैं। हमें उम्मीद है कि आपको यह ट्यूटोरियल मददगार लगा होगा।