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 post order traversal
void postorderTraversal(Node*);
//moving in a sorted manner using 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);
}
void convert_BSTHeap(Node* root, vector<int> arr, int* i){
   if (root == NULL)
      return;
   convert_BSTHeap(root->left, arr, i);
   convert_BSTHeap(root->right, arr, i);
   //copying data from array to node
   root->data = arr[++*i];
}
//converting to max heap
void convert_maxheap(Node* root) {
   vector<int> arr;
   int i = -1;
   inorderTraversal(root, arr);
   convert_BSTHeap(root, arr, &i);
}
//printing post order traversal
void postorderTraversal(Node* root) {
   if (!root)
      return;
   postorderTraversal(root->left);
   postorderTraversal(root->right);
   cout << root->data << " ";
}
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_maxheap(root);
   cout << "Postorder Traversal:" << endl;
   postorderTraversal(root);
   return 0;
}

出力

Postorder Traversal:
1 2 3 4 5 6 7