Cho BST, chuyển thành Min Heap sao cho thứ tự duyệt preorder của Min Heap bằng thứ tự inorder của BST (tăng dần).
Giải pháp: Inorder BST -> mảng đã sắp xếp. Preorder traversal cây, gán giá trị từ mảng theo thứ tự.
Chương trình minh họa
#include <bits/stdc++.h>
using namespace std;
struct Node { int data; Node *left, *right; };
Node* getNode(int data){
Node* n = new Node; n->data = data; n->left = n->right = NULL; return n;
}
void inorderTraversal(Node* root, vector<int>& arr){
if (!root) return;
inorderTraversal(root->left, arr);
arr.push_back(root->data);
inorderTraversal(root->right, arr);
}
void convert_BSPheap(Node* root, vector<int> arr, int* i){
if (!root) return;
root->data = arr[++(*i)];
convert_BSPheap(root->left, arr, i);
convert_BSPheap(root->right, arr, i);
}
void convert_minheap(Node* root){
vector<int> arr; int i = -1;
inorderTraversal(root, arr);
convert_BSPheap(root, arr, &i);
}
void preorderTraversal(Node* root){
if (!root) return;
cout << root->data << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
int main(){
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 (Min Heap):\n";
preorderTraversal(root);
return 0;
}
Kết quả
Preorder Traversal: 1 2 3 4 5 6 7