Code C++ pour inverser les chemins dans un arbre de recherche binaire à l'aide de files d'attente

Par exemple, étant donné un arbre de recherche binaire, nous devons inverser son chemin à partir d'une clé spécifique.

Façon de trouver une solution

Dans cette méthode, nous allons créer une file d'attente et pousser tous les nœuds jusqu'à ce que nous obtenions le nœud racine.

p>

Exemple

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

Sortie

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

Explication du code ci-dessus

Dans cette méthode, nous recherchons simplement la clé donnée. Lorsque nous parcourons l'arbre, nous mettons tous les nœuds dans une file d'attente et maintenant, lorsque nous trouvons le nœud avec la valeur clé, nous échangeons les valeurs de tous les nœuds de chemin qui nous ont précédés et, ce faisant, notre chemin

Conclusion

Nous avons résolu le problème de l'inversion des chemins dans BST en utilisant des files d'attente et la récursivité. Nous avons également appris le programme C++ pour ce problème et la méthode complète (générique) pour le résoudre. Nous pouvons écrire le même programme dans d'autres langages tels que C, Java, Python et d'autres langages. Nous espérons que vous avez trouvé ce tutoriel utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!