एक बाइनरी सर्च ट्री दिया गया है, और हमें एक विशेष कुंजी से इसके पथ को उल्टा करना आवश्यक है, उदाहरण के लिए।
समाधान खोजने का दृष्टिकोण
इस दृष्टिकोण में, हम एक क्यू बनाएंगे और रूट मिलने तक सभी नोड्स को पुश करेंगे।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
struct node {
int key;
struct node *left, *right;
};
struct node* newNode(int item){
struct node* temp = new node;
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
void inorder(struct node* root){
if (root != NULL) {
inorder(root->left);
cout << root->key << " ";
inorder(root->right);
}
}
void Reversing(struct node** node, int& key, queue<int>& q1){
/* यदि ट्री खाली है तो
रिटर्न*/
if (node == NULL)
return;
if ((*node)->key == key){ // यदि हमें कुंजी मिल जाती है
q1.push((*node)->key); // हम इसे अपनी क्यू में पुश करते हैं
(*node)->key = q1.front(); // हम वर्तमान के साथ पहली क्यू तत्व को बदलते हैं
q1.pop(); // हम पहला तत्व पॉप करते हैं
}
else if (key < (*node)->key){ // यदि कुंजी वर्तमान नोड के मान से कम है
q1.push((*node)->key); // हम तत्व को अपनी क्यू में पुश करते हैं
Reversing(&(*node)->left, key, q1); // हम रिकर्सिव कॉल का उपयोग करके बाएं सबट्री में जाते हैं
(*node)->key = q1.front(); // हम तत्वों को उल्टा करते हैं
q1.pop(); // हम पहला तत्व पॉप करते हैं
}
else if (key > (*node)->key){ // यदि कुंजी नोड कुंजी से अधिक है तो
q1.push((*node)->key); // हम नोड कुंजी को क्यू में पुश करते हैं
Reversing(&(*node)->right, key, q1); // हम रिकर्सिव कॉल का उपयोग करके दाएं सबट्री में जाते हैं
(*node)->key = q1.front(); // क्यू फ्रंट को नोड कुंजी से बदलें
q1.pop(); // हम पहला तत्व पॉप करते हैं
}
return;
}
struct node* insert_node(struct node* node, // हमारे BST में नोड डालने का फंक्शन
int key){
if (node == NULL)
return newNode(key); // यदि ट्री खाली है तो हम एक नया नोड रिटर्न करते हैं
if (key < node->key) // अन्यथा हम इसे अपने ट्री में पुश करते हैं
node->left = insert_node(node->left, key);
else if (key > node->key)
node->right = insert_node(node->right, key);
return node; // नोड रिटर्न करना
}
int main(){
struct node* root = NULL;
queue<int> q1;
int k = 80;
/****************BST बनाना*************************/
root = insert_node(root, 50);
insert_node(root, 30);
insert_node(root, 20);
insert_node(root, 40);
insert_node(root, 70);
insert_node(root, 60);
insert_node(root, 80);
cout << "उल्टा करने से पहले :" << "\n";
inorder(root);
cout << "\n";
Reversing(&root, k, q1);
cout << "उल्टा करने के बाद :" << "\n";
// रिवर्स पथ ट्री का इनऑर्डर प्रिंट करना
inorder(root);
return 0;
}
आउटपुट
उल्टा करने से पहले: 20 30 40 50 60 70 80 उल्टा करने के बाद: 20 30 40 80 60 70 50
उपरोक्त कोड की व्याख्या
इस दृष्टिकोण में, हम केवल दी गई कुंजी को खोजने जा रहे हैं। जैसे-जैसे हम ट्री के माध्यम से जाते हैं, हम सभी नोड्स को एक क्यू में पुश करते हैं, और अब जब हमें कुंजी के मान वाला नोड मिल जाता है, तो हम उन सभी पथ नोड्स के मान को स्वैप करते हैं जो क्यू में फ्रंट पर हैं, और इस प्रक्रिया में हमारा पथ उल्टा हो जाता है।
निष्कर्ष
हम क्यू और रिकर्सन का उपयोग करके BST में एक पथ को उल्टा करने की समस्या को हल करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और इसे हल करने के पूर्ण दृष्टिकोण (सामान्य) को भी सीखा। हम इसी प्रोग्राम को C, Java, Python और अन्य भाषाओं में लिख सकते हैं। आशा है कि आपको यह ट्यूटोरियल मददगार लगा होगा।
