BST ਨੂੰ ਮਿਨ ਹੀਪ ਵਿੱਚ ਬਦਲੋ  


ਮੁਸ਼ਕਲ ਪੱਧਰ ਹਾਰਡ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ ਬਲੈਕਰੋਕ ਬਾਈਟਡੈਂਸ GE ਹੈਲਥਕੇਅਰ ਹਨੀਵੈੱਲ
ਬਾਈਨਰੀ ਖੋਜ ਲੜੀ ਬਾਈਨਰੀ ਟਰੀ Apੇਰ ਟ੍ਰੀ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ  

ਇੱਕ ਸੰਪੂਰਨ ਦਿੱਤਾ ਬਾਈਨਰੀ ਖੋਜ ਲੜੀ, ਇਸ ਨੂੰ ਏ ਵਿਚ ਬਦਲਣ ਲਈ ਇਕ ਐਲਗੋਰਿਦਮ ਲਿਖੋ ਮਿਨ apੇਰ, ਜੋ ਕਿ ਬੀ ਐਸ ਟੀ ਨੂੰ ਮਿਨ ਹੀਪ ਵਿੱਚ ਬਦਲਣਾ ਹੈ. ਮਿਨ ਹੀਪ ਅਜਿਹਾ ਹੋਣਾ ਚਾਹੀਦਾ ਹੈ ਕਿ ਨੋਡ ਦੇ ਖੱਬੇ ਪਾਸੇ ਦੇ ਮੁੱਲ ਉਸ ਨੋਡ ਦੇ ਸੱਜੇ ਮੁੱਲ ਤੋਂ ਘੱਟ ਹੋਣੇ ਚਾਹੀਦੇ ਹਨ.

ਉਦਾਹਰਨ  

ਇੰਪੁੱਟ

BST ਨੂੰ ਮਿਨ ਹੀਪ ਵਿੱਚ ਬਦਲੋਪਿੰਨ

ਆਉਟਪੁੱਟ

BST ਨੂੰ ਮਿਨ ਹੀਪ ਵਿੱਚ ਬਦਲੋਪਿੰਨਪਿੰਨ

ਪੱਧਰ ਦਾ ਆਰਡਰ: 6 7 13 9 12 18 23

ਬੀ ਐਸ ਟੀ ਨੂੰ ਮਿਨ ਹੀਪ ਵਿੱਚ ਬਦਲਣ ਲਈ ਐਲਗੋਰਿਦਮ  

ਇੱਕ ਬਾਈਨਰੀ ਸਰਚ ਟਰੀ ਵਿੱਚ ਅਜਿਹੇ ਤੱਤ ਹੁੰਦੇ ਹਨ ਜੋ ਇਸਦੇ 'ਇਨ-ਆਰਡਰ ਟ੍ਰਾਵਰਸਲ ਐਲੀਮੈਂਟਸ ਨੂੰ ਸੌਰਟਡ ਰੂਪ ਵਿੱਚ ਦਿੰਦੇ ਹਨ. ਬੀ ਐਸ ਟੀ ਨੂੰ ਮਿਨ ਹੀਪ ਵਿੱਚ ਬਦਲਣ ਲਈ ਅਸੀਂ ਬਾਈਨਰੀ ਸਰਚ ਟਰੀ ਦੇ ਇਨ-ਆਰਡਰ ਟ੍ਰਾਵਰਸਾਲ ਨੂੰ ਪ੍ਰੀ-ਆਰਡਰ ਟ੍ਰਾਵਰਸਲ ਵਿੱਚ ਬਦਲਦੇ ਹਾਂ, ਭਾਵ, ਅਸੀਂ ਰੁੱਖ ਦੇ ਇਨ-ਆਰਡਰ ਟ੍ਰਾਵਰਸਲ ਨੂੰ ਇੱਕ ਐਰੇ ਵਿੱਚ ਸਟੋਰ ਕਰਦੇ ਹਾਂ ਅਤੇ ਫਿਰ ਨੋਡਾਂ ਨੂੰ ਪ੍ਰੀ-ਆਰਡਰ ਫੈਸ਼ਨ ਵਿੱਚ ਬਦਲਦੇ ਹਾਂ. ਇਨ-ਆਰਡਰ ਆਉਟਪੁੱਟ ਦੇ ਨਾਲ.

ਇਹ ਸੁਨਿਸ਼ਚਿਤ ਕਰੇਗਾ ਕਿ ਬਾਈਨਰੀ ਸਰਚ ਟ੍ਰੀ ਇੱਕ ਮਿਨ ਹੀਪ ਵਿੱਚ ਤਬਦੀਲ ਹੋ ਜਾਂਦੀ ਹੈ ਅਤੇ ਮਿਨ ਹੀਪ ਦਿੱਤੀ ਗਈ ਜਾਇਦਾਦ ਨੂੰ ਸੰਤੁਸ਼ਟ ਵੀ ਕਰਦਾ ਹੈ, ਭਾਵ, ਨੋਡ ਦੇ ਖੱਬੇ ਉਪ-ਰੁੱਖ ਦੇ ਸਾਰੇ ਨੋਡ ਸੱਜੇ ਉਪ-ਰੁੱਖ ਦੇ ਸਾਰੇ ਨੋਡਾਂ ਤੋਂ ਛੋਟੇ ਹਨ. ਉਸ ਰੁੱਖ ਦਾ.

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.

ਟਾਈਮ ਜਟਿਲਤਾ = ਓ (ਐਨ)

ਕਿਉਂਕਿ ਅਸੀਂ ਦਰੱਖਤ ਦੇ ਕ੍ਰਮ ਅਤੇ ਪੂਰਵ-ਆਰਡਰ ਟ੍ਰਾਵਰਸਾਲ ਪ੍ਰਦਰਸ਼ਨ ਕੀਤਾ ਹੈ ਜੋ ਸਿਰਫ ਓ (ਐਨ) ਸਮਾਂ ਲੈਂਦਾ ਹੈ.

ਇਹ ਵੀ ਵੇਖੋ
ਡੁਪਲੀਕੇਟ ਸਬਟ੍ਰੀਜ਼ ਲੱਭੋ

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ = ਓ (ਐਨ)

ਇੱਥੇ ਅਸੀਂ n ਐਲੀਮੈਂਟਸ ਸਟੋਰ ਕਰ ਰਹੇ ਹਾਂ, ਇਸ ਤਰ੍ਹਾਂ ਇੱਕ ਲੀਨੀਅਰ ਸਪੇਸ ਗੁੰਝਲਦਾਰਤਾ ਸਪੇਸ ਸਲਿ /ਸ਼ਨ /.
ਜਿੱਥੇ N ਸੰਪੂਰਨ ਬਾਈਨਰੀ ਖੋਜ ਲੜੀ ਵਿੱਚ ਨੋਡਾਂ ਦੀ ਕੁੱਲ ਸੰਖਿਆ ਹੈ.

ਕਥਾ

ਉਪਰੋਕਤ ਉਦਾਹਰਣ ਵਿੱਚ ਦਰਸਾਏ ਗਏ ਰੁੱਖ ਉੱਤੇ ਗੌਰ ਕਰੋ.

ਕਦਮ 1
ਰੁੱਖ ਨੂੰ ਕ੍ਰਮ ਵਿੱਚ ਭੇਜੋ ਅਤੇ ਇਸ ਨੂੰ ਐਰੇ ਵਿੱਚ ਸਟੋਰ ਕਰੋ.
ਅਰੁ [] = {6, 7, 9, 12, 13, 18, 23}

ਕਦਮ 2 ਅਤੇ 3
ਦਰੱਖਤ ਨੂੰ ਪ੍ਰੀ-ਆਰਡਰ ਦੇ ਰੂਪ ਵਿਚ ਪਾਰ ਕਰੋ ਅਤੇ ਹਰ ਨੋਡ ਦੇ ਮੁੱਲ ਨੂੰ ਐਰੇ ਵਿਚ ਸਟੋਰ ਕੀਤੇ ਅਨੁਸਾਰੀ ਮੁੱਲ ਨਾਲ ਬਦਲੋ.

BST ਨੂੰ ਮਿਨ ਹੀਪ ਵਿੱਚ ਬਦਲੋਪਿੰਨਪਿੰਨ

ਜਿਵੇਂ ਕਿ ਅਸੀਂ ਚਿੱਤਰ ਵਿਚ ਵੇਖ ਸਕਦੇ ਹਾਂ, ਦਰੱਖਤ ਦਿੱਤੀ ਗਈ ਵਿਸ਼ੇਸ਼ਤਾਵਾਂ ਨੂੰ ਸੰਤੁਸ਼ਟ ਕਰਦੇ ਹੋਏ ਮਿਨ Heੇਰ ਵਿਚ ਤਬਦੀਲ ਹੋ ਗਿਆ ਹੈ.

ਕੋਡ  

ਜਾਵਾ ਕੋਡ ਬੀ ਐਸ ਟੀ ਨੂੰ ਮਿਨ ਹੀਪ ਵਿੱਚ ਬਦਲਣ ਲਈ

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

ਬੀਐਸਟੀ ਨੂੰ ਮਿਨ ਹੀਪ ਵਿੱਚ ਬਦਲਣ ਲਈ ਸੀ ++ ਕੋਡ

#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