BST-ті Min Heap-ге ауыстыру


Күрделілік дәрежесі қиын
Жиі кіреді Amazon BlackRock ByteDance GE Healthcare Honeywell
Екілік іздеу ағашы Екілік ағаш Үйінді ағаш

Проблемалық мәлімдеме

Толық берілген Екілік іздеу ағашы, оны а-ға айналдыру алгоритмін жазыңыз Мин үйме, бұл BST-ті Min Heap-ге айналдыру. Мин үйіндісі түйіннің сол жағындағы мәндер сол түйіннің оң жағындағы мәндерден аз болуы керек.

мысал

енгізу

BST-ті Min Heap-ге ауыстыру

шығыс

BST-ті Min Heap-ге ауыстыру

Деңгейлік тапсырыс: 6 7 13 9 12 18 23

BST-ді Min Heap-ге айналдыру алгоритмі

Екілік іздеу ағашы элементтерді қамтиды, олардың 'ретпен өтуі элементтерді сұрыпталған түрде береді. BST-ті Min Heap-ге ауыстыру үшін біз алдын-ала траверсте екілік іздеу ағашының ретпен өтуін өзгертеміз, яғни массивте ағаштың траекториясын сақтаймыз, содан кейін түйіндерді алдын-ала тапсырыс түрінде ауыстырамыз тапсырыс бойынша шығарумен.

Бұл екілік іздеу ағашының Min Heap-ге айналуын қамтамасыз етеді, сонымен қатар Min Heap берілген қасиетті қанағаттандырады, яғни түйіннің сол жақ ішкі ағашындағы барлық түйіндер оң жақ ішкі ағаштағы барлық түйіндерден кішірек сол ағаш.

1. Traverse the BST in in-order traversal and store the traversal in an array or a list.
2. This time traverse the Binary Search Tree in pre-order form.
3. Replace every node with the corresponding value stored in the array or list.

Уақыттың күрделілігі = O (N)

Біз тек O (N) уақытты қажет ететін ағаш траверстері бойынша тәртіптелген және алдын-ала тапсырыс бергендіктен.

Ғарыштың күрделілігі = O (N)

Мұнда біз n элементті сақтаймыз, осылайша сызықтық кеңістіктің күрделілігі кеңістік шешімі /.
мұндағы N - толық екілік іздеу ағашындағы түйіндердің жалпы саны.

Түсіндіру

Жоғарыда келтірілген мысалда көрсетілген ағашты қарастырайық.

қадам 1
Ағашты тәртіп бойынша айналып өтіп, оны массивте сақтаңыз.
arr [] = {6, 7, 9, 12, 13, 18, 23}

2 & 3 қадам
Алдын ала тапсырыс түрінде ағашты айналып өтіп, әрбір түйіннің мәнін массивте сақталған сәйкес мәнмен ауыстырыңыз.

BST-ті Min Heap-ге ауыстыру

Суреттен көріп отырғанымыздай, ағаш берілген қасиеттерді қанағаттандыратын Min үйіндіге айналады.

код

BST-ті Min Heap-ге ауыстыратын Java коды

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
class ConvertBSTToMinHeap {
    // class representing node of a binary tree
    static class Node {
        int data;
        Node left, right;
        public Node(int data) {
            this.data = data;
        }
    }
    // function to print level order traversal of binary tree
    private static void levelOrder(Node root) {
        if (root == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node curr = queue.poll();
            System.out.print(curr.data + " ");
            if (curr.left != null)
                queue.add(curr.left);
            if (curr.right != null)
                queue.add(curr.right);
        }
    }
    // function to store the inorder traversal of tree in a list
    private static void storeInOrder(Node root, ArrayList<Integer> inOrder) {
        if (root != null) {
            storeInOrder(root.left, inOrder);
            inOrder.add(root.data);
            storeInOrder(root.right, inOrder);
        }
    }
    // function to replace the inorder traversal with pre-order traversal
    private static void replaceInOrderWithPreOrder(Node root, ArrayList<Integer> inOrder) {
        if (root != null) {
            root.data = inOrder.get(0);
            inOrder.remove(0);
            replaceInOrderWithPreOrder(root.left, inOrder);
            replaceInOrderWithPreOrder(root.right, inOrder);
        }
    }
    private static void convertToMinHeap(Node root) {
        ArrayList<Integer> inOrderTraversal = new ArrayList<>();
        // store the in order traversal of the tree in a list
        storeInOrder(root, inOrderTraversal);
        // replace the pre order traversal with in order traversal
        replaceInOrderWithPreOrder(root, inOrderTraversal);
    }
    public static void main(String[] args) {
        // Example Tree
        Node root = new Node(12);
        root.left = new Node(7);
        root.right = new Node(18);
        root.left.left = new Node(6);
        root.left.right = new Node(9);
        root.right.left = new Node(13);
        root.right.right = new Node(23);
        convertToMinHeap(root);
        levelOrder(root);
        System.out.println();
    }
}
6 7 13 9 12 18 23

BST-ті Min Heap-ге ауыстыру үшін C ++ коды

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

// class representing node of a binary tree 
class Node { 
    public: 
    int data; 
    Node *left; 
    Node *right; 
    
    Node(int d) { 
        data = d; 
        left = right = NULL; 
    } 
};

// function to print level order traversal of binary tree
void levelOrder(Node *root) {
    if (root == NULL) {
        return;
    }
    
    queue<Node*> q;
    q.push(root);
    
    while (!q.empty()) {
        Node *curr = q.front();
        q.pop();
        
        cout<<curr->data<<" ";
        
        if (curr->left != NULL)
            q.push(curr->left);
        if (curr->right != NULL) 
            q.push(curr->right);
    }
}


// function to store the inorder traversal of tree in a list
void storeInOrder(Node *root, vector<int> &inOrderTraversal) {
    if (root != NULL) {
        storeInOrder(root->left, inOrderTraversal);
        inOrderTraversal.push_back(root->data);
        storeInOrder(root->right, inOrderTraversal);
    }
}

// function to replace the inorder traversal with pre-order traversal
void replaceInOrderWithPreOrder(Node *root, vector<int> &inOrderTraversal) {
    if (root != NULL) {
        root->data = inOrderTraversal[0];
        inOrderTraversal.erase(inOrderTraversal.begin());
        replaceInOrderWithPreOrder(root->left, inOrderTraversal);
        replaceInOrderWithPreOrder(root->right, inOrderTraversal);
    }
}

void convertToMinHeap(Node *root) {
    std::vector<int> inOrderTraversal;
    
    // store the in order traversal of the tree in a list
    storeInOrder(root, inOrderTraversal);
    
    // replace the pre order traversal with in order traversal
    replaceInOrderWithPreOrder(root, inOrderTraversal);
}

int main() {
    // Example Tree
    Node *root = new Node(12);
    root->left = new Node(7);
    root->right = new Node(18);
    root->left->left = new Node(6);
    root->left->right = new Node(9);
    root->right->left = new Node(13);
    root->right->right = new Node(23);

    convertToMinHeap(root);
    levelOrder(root);
    cout<<endl;
    
    return 0;
}
6 7 13 9 12 18 23