Kod C++ untuk membalikkan laluan dalam pepohon carian binari menggunakan baris gilir

Sebagai contoh, diberikan pepohon carian binari, kita perlu membalikkan laluannya daripada kunci tertentu.

Cara untuk mencari penyelesaian

#🎜🎜🎜, kita #Dalam kaedah ini akan membuat baris gilir dan menolak semua nod sehingga kita mendapat nod akar.

p>

Contoh

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

Output

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

Penjelasan kod di atas

🎜🎜🎜 , kita hanya perlu mencari kunci yang diberikan. Apabila kami melintasi pokok, kami meletakkan semua nod ke dalam baris gilir, kini apabila kami menemui nod dengan nilai kunci, kami menukar nilai semua nod laluan yang berada di hadapan, dalam proses itu, laluan kami #🎜🎜 #

Kesimpulan

Kami menyelesaikan masalah membalikkan laluan dalam BST menggunakan baris gilir dan ulangan. Kami juga mempelajari program C++ untuk masalah ini dan kaedah lengkap (generik) untuk menyelesaikannya. Kita boleh menulis program yang sama dalam bahasa lain seperti C, java, python dan bahasa lain. Kami harap anda mendapati tutorial ini membantu.

Atas ialah kandungan terperinci Kod C++ untuk membalikkan laluan dalam pepohon carian binari menggunakan baris gilir. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!