Chuyển đổi BST thành Max Heap trong C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để chuyển đổi cây tìm kiếm nhị phân thành một đống tối đa.

Đối với điều này, chúng tôi sẽ được cung cấp một cây tìm kiếm nhị phân. Nhiệm vụ của chúng tôi là chuyển đổi cây tìm kiếm nhị phân đã cho thành một đống tối đa sao cho tuân theo điều kiện của cây tìm kiếm nhị phân khi các phần tử được so sánh với chính chúng.

Ví dụ

#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;
}

Đầu ra

Postorder Traversal:
1 2 3 4 5 6 7