Փոխակերպել BST- ն Min Heap- ի  


Դժվարության մակարդակ Դժվար
Հաճախակի հարցնում են Amazon Blackrock ByteDance GE Healthcare HONEYWELL
Երկուական որոնման ծառ Երկուական ծառ Կույտ ծառ

Խնդիրի հայտարարություն  

Հաշվի առնելով ամբողջական Երկուական որոնման ծառ, գրեք ալգորիթմ `այն a- ի վերածելու համար Մին կույտ, որը պետք է BST- ն վերածի Min Heap- ի: 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.

Timeամանակի բարդություն = ՎՐԱ)

Քանի որ մենք կատարեցինք ծառի պատվերով և նախնական պատվերով անցումներ, որոնք տևում են միայն O (N) ժամանակ:

Տես նաեւ,
Գտեք Կրկնօրինակ ենթատետրեր

Տիեզերական բարդություն = ՎՐԱ)

Այստեղ մենք պահպանում ենք n տարրեր, այդպիսով գծային տարածության բարդության տիեզերական լուծում /:
որտեղ N- ը Երկուական որոնման ամբողջական ծառի հանգույցների ընդհանուր թիվն է:

բացատրություն

Դիտարկենք վերը նշված օրինակում ներկայացված ծառը:

Քայլ 1
Անցեք ծառը պատվերի տեսքով և պահեք այն զանգվածում:
arr [] = {6, 7, 9, 12, 13, 18, 23}

Քայլ 2 և 3
Անցեք ծառը նախնական պատվերով և յուրաքանչյուր հանգույցի արժեքը փոխարինեք զանգվածում պահված համապատասխան արժեքով:

Փոխակերպել BST- ն Min Heap- ի

Ինչպես տեսնում ենք նկարում, ծառը վերածվում է տրված հատկությունները բավարարող Min Heap- ի:

Կոդ  

Java կոդ ՝ BST- ը Min Heap փոխակերպելու համար

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

C ++ կոդ ՝ BST- ը Min Heap փոխակերպելու համար

#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