सी ++ कतार का उपयोग करके बीएसटी में पथ को उलट दें

एक बाइनरी सर्च ट्री को देखते हुए, और उदाहरण के लिए, हमें किसी विशेष कुंजी से इसके पथ को उलटने की आवश्यकता होती है।

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

इस दृष्टिकोण में, हम एक कतार बनाएंगे और सभी नोड्स को तब तक धकेलेंगे जब तक हमें रूट नहीं मिल जाता।

उदाहरण

 
#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 the tree is empty then
   return*/
   if (node == NULL)
       return;
   if ((*node)->key == key){ // if we find the key
       q1.push((*node)->key); // we push it into our queue
       (*node)->key = q1.front(); // we change the first queue element with current
       q1.pop(); // we pop the first element
   }
   else if (key < (*node)->key){ // if key is less than current node's value
       q1.push((*node)->key); // we push the element in our queue
       Reversing(&(*node)->left, key, q1); //we go to the left subtree using a recursive call
       (*node)->key = q1.front(); //we reverse the elements
       q1.pop(); // we pop the first element
   }
   else if (key > (*node)->key){ // if key greater than node key then
       q1.push((*node)->key);// we push node key into queue
       Reversing(&(*node)->right, key, q1);// we go to right subtree using a recursive call
       (*node)->key = q1.front();// replace queue front to node key
       q1.pop(); // we pop the first element
   }
   return;
}
struct node* insert_node(struct node* node, // function to insert node nodes in our BST
                           int key){
   if (node == NULL)
       return newNode(key); // if tree is empty we return a new node
   if (key < node->key) // else we push that in our tree
       node->left = insert_node(node->left, key);
   else if (key > node->key)
       node->right = insert_node(node->right, key);
   return node; // returning the node
}
int main(){
   struct node* root = NULL;
   queue<int> q1;
   int k = 80;
/****************Creating the 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 << "Before Reversing :" << "\n";
   inorder(root);
   cout << "\n";
   Reversing(&root, k, q1);
   cout << "After Reversing :" << "\n";
   // print inorder of reverse path tree
   inorder(root);
   return 0;
}

आउटपुट

Before Reversing :
20 30 40 50 60 70 80
After Reversing :
20 30 40 80 60 70 50

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

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

निष्कर्ष

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