C++-Code zum Umkehren von Pfaden in einem binären Suchbaum mithilfe von Warteschlangen

Bei einem gegebenen binären Suchbaum müssen wir beispielsweise seinen Pfad von einem bestimmten Schlüssel aus umkehren.

Weg zur Lösung

Bei dieser Methode erstellen wir eine Warteschlange und pushen alle Knoten, bis wir den Wurzelknoten erhalten.

p>

Beispiel

 
#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&#39;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;
}

Ausgabe

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

Erklärung des obigen Codes

In dieser Methode suchen wir einfach nach dem angegebenen Schlüssel. Wenn wir den Baum durchqueren, stellen wir alle Knoten in eine Warteschlange und wenn wir nun den Knoten mit dem Schlüsselwert finden, tauschen wir die Werte aller Pfadknoten aus, die vor uns kamen, und dabei unseren Pfad

Fazit

Wir haben das Problem der Pfadumkehr in BST mithilfe von Warteschlangen und Rekursion gelöst. Wir haben auch das C++-Programm für dieses Problem und die vollständige (generische) Methode zur Lösung gelernt. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen Sprachen schreiben. Wir hoffen, dass Sie dieses Tutorial hilfreich fanden.

Das obige ist der detaillierte Inhalt vonC++-Code zum Umkehren von Pfaden in einem binären Suchbaum mithilfe von Warteschlangen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!