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

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

สำหรับนี้ เราจะได้รับ binary search tree งานของเราคือแปลง BST ที่กำหนดให้เป็น min 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;
}

// preorder traversal
void preorderTraversal(Node*);

// เก็บค่าแบบเรียงลำดับด้วย 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);
}

// แปลง BST เป็น 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);
}

// แปลงเป็น min heap
void convert_minheap(Node *root) {
    // vector เก็บค่าของโหนด
    vector<int> arr;
    int i = -1;
    // ท่อง inorder
    inorderTraversal(root, arr);
    convert_BSPheap(root, arr, &i);
}

// 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