큐를 사용하여 이진 검색 트리에서 경로를 바꾸는 C++ 코드

예를 들어 이진 검색 트리가 있는 경우 특정 키의 경로를 바꿔야 합니다.

솔루션을 찾는 방법

이 방법에서는 큐를 만들고 루트 노드를 얻을 때까지 모든 노드를 푸시합니다.

p>

Example

 
#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

위 코드 설명

이 방법에서는 주어진 키만 검색합니다. 트리를 순회할 때 모든 노드를 대기열에 넣고 이제 키 값이 있는 노드를 찾으면 이전에 온 모든 경로 노드의 값과 그 과정에서 경로를 교환합니다

결론

큐와 재귀를 사용하여 BST의 경로 반전 문제를 해결했습니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이를 해결하기 위한 완전한 방법(일반)을 배웠습니다. C, Java, Python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 튜토리얼이 도움이 되었기를 바랍니다.

위 내용은 큐를 사용하여 이진 검색 트리에서 경로를 바꾸는 C++ 코드의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!