C++에서 BST를 최소 힙으로 변환

이 자습서에서는 이진 검색 트리를 최소 힙으로 변환하는 프로그램에 대해 설명합니다.

이를 위해 이진 검색 트리가 제공됩니다. 우리의 임무는 주어진 이진 검색 트리를 최소 힙으로 변환하여 요소가 자신과 비교될 때 이진 검색 트리의 조건을 따르도록 하는 것입니다.

예시

#include <bits/stdc++.h>
using namespace std;
//node structure of BST
struct Node {
   int data;
   Node *left, *right;
};
//node creation
struct Node* getNode(int data) {
   struct Node *newNode = new Node;
   newNode->data = data;
   newNode->left = newNode->right = NULL;
   return newNode;
}
//performing preorder traversal
void preorderTraversal(Node*);
//storing values in sorted fashion
//with inorder traversal
void inorderTraversal(Node *root, vector<int>& arr) {
   if (root == NULL)
      return;
   inorderTraversal(root->left, arr);
   arr.push_back(root->data);
   inorderTraversal(root->right, arr);
}
//converting BST to min heap
void convert_BSPheap(Node *root, vector<int> arr, int *i) {
   if (root == NULL)
      return;
   root->data = arr[++*i];
   convert_BSPheap(root->left, arr, i);
   convert_BSPheap(root->right, arr, i);
}
//converting to min heap
void convert_minheap(Node *root) {
   //vector storing the values of nodes
   vector<int> arr;
   int i = -1;
   //moving via inorder traversal
   inorderTraversal(root, arr);
   convert_BSPheap(root, arr, &i);
}
//performing preorder traversal
void preorderTraversal(Node *root) {
   if (!root)
    return;
   cout << root->data << " ";
   preorderTraversal(root->left);
   preorderTraversal(root->right);
}
int main() {
   struct Node *root = getNode(4);
   root->left = getNode(2);
   root->right = getNode(6);
   root->left->left = getNode(1);
   root->left->right = getNode(3);
   root->right->left = getNode(5);
   root->right->right = getNode(7);
   convert_minheap(root);
   cout << "Preorder Traversal:" << endl;
   preorderTraversal(root);
   return 0;
}

출력

Preorder Traversal:
1 2 3 4 5 6 7