C++ 使用队列反转 BST 中的路径
c++server side programmingprogramming
给定一个二叉搜索树，我们需要从特定键反转其路径，例如。
寻找解决方案的方法
在这种方法中，我们将创建一个队列并推送所有节点，直到我们得到根。
示例
#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){
/* 如果树为空则
return*/
if (node == NULL)
return;
if ((*node)->key == key){ // 如果我们找到密钥
q1.push((*node)->key); // 我们将其推送到队列中
(*node)->key = q1.front(); // 我们用当前元素替换第一个队列元素
q1.pop(); // 我们弹出第一个元素
}
else if (key < (*node)->key){ // 如果 key 小于当前节点的值
q1.push((*node)->key); // 我们将元素推送到队列中
Reversing(&(*node)->left, key, q1); // 我们使用递归调用转到左子树
(*node)->key = q1.front(); // 我们反转元素
q1.pop(); // 我们弹出第一个元素
}
else if (key > (*node)->key){ // 如果 key 大于节点 key 则
q1.push((*node)->key);// 我们将节点 key 推送到队列中
Reversing(&(*node)->right, key, q1);// 我们使用递归调用转到右子树
(*node)->key = q1.front();// 将队列前端替换为节点 key
q1.pop(); // 我们弹出第一个元素
}
return;
}
struct node* insert_node(struct node* node, // 在我们的 BST 中插入节点的函数
int key){
if (node == NULL)
return newNode(key); // 如果树为空，则返回一个新节点
if (key < node->key) // 否则，我们将其推送到树中
node->left = insert_node(node->left, key);
else if (key > node->key)
node->right = insert_node(node->right, key);
return 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 << "反转前:<< "\n";
inorder(root);
cout << "\n";
Reversing(&root, k, q1);
cout << "反转后:<< "\n";
// 打印反向路径树的中序
inorder(root);
return 0;
}
输出
反转前: 20 30 40 50 60 70 80 反转后: 20 30 40 80 60 70 50
上述代码的解释
在这种方法中，我们只需搜索给定的键。当我们遍历树时，我们将所有节点推送到队列中，现在当我们找到具有键值的节点时，我们交换所有排在前面的路径节点的值，在此过程中，我们的路径被反转。
结论
我们使用队列和递归解决了 BST 中反转路径的问题。我们还学习了这个问题的 C++ 程序和我们解决这个问题的完整方法(正常)。我们可以用其他语言(例如 C、java、python 和其他语言)编写相同的程序。我们希望您觉得本教程有用。
