Ví dụ:đưa ra một cây tìm kiếm nhị phân và chúng tôi buộc phải đảo ngược đường dẫn của nó từ một khóa cụ thể.
Phương pháp tiếp cận để tìm giải pháp
Trong cách tiếp cận này, chúng tôi sẽ tạo một hàng đợi và đẩy tất cả các nút cho đến khi chúng tôi nhận được gốc.
Ví dụ
#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;
} Đầu ra
Before Reversing : 20 30 40 50 60 70 80 After Reversing : 20 30 40 80 60 70 50
Giải thích về Quy tắc trên
Trong cách tiếp cận này, chúng tôi chỉ đơn giản là sẽ tìm kiếm khóa đã cho. Khi chúng ta đi qua cây, chúng ta đẩy tất cả các nút vào một hàng đợi và bây giờ khi chúng ta tìm thấy nút có giá trị của khóa, chúng ta hoán đổi tất cả các giá trị của các nút đường dẫn mà chúng ta xếp hàng trước và trong quá trình này, đường dẫn của chúng ta bị đảo ngược.
Kết luận
Chúng tôi giải quyết một vấn đề để Đảo ngược một đường dẫn trong BST bằng cách sử dụng hàng đợi và sử dụng đệ quy. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.