แปลง BST เป็น Max Heap ใน C++

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมแปลง binary search tree เป็น max heap

สำหรับนี้ เราจะได้รับ binary search tree งานของเราคือแปลง BST ที่กำหนดให้เป็น max heap โดยที่เงื่อนไขของ BST ยังคงเป็นจริงเมื่อเปรียบเทียบองค์ประกอบกับตัวเอง

โปรแกรมตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

// โครงสร้างโหนดของ BST
struct Node {
    int data;
    Node *left, *right;
};

// สร้างโหนด
struct Node* getNode(int data) {
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// postorder traversal
void postorderTraversal(Node*);

// ท่อง inorder เพื่อเรียงลำดับ
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);
    // copy ข้อมูลจาก array ไปโหนด
    root->data = arr[++*i];
}

// แปลงเป็น max heap
void convert_maxheap(Node* root) {
    vector<int> arr;
    int i = -1;
    inorderTraversal(root, arr);
    convert_BSTHeap(root, arr, &i);
}

// พิมพ์ postorder 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