Табдил додан BST ба Min Heap


Сатҳи душворӣ мушкил
Аксар вақт пурсида мешавад Amazon BlackRock ByteDance GE Тандурустӣ Honeywell
Дарахти ҷустуҷӯи бинарӣ Дарахти дуӣ Андозаи Дарахт

Изҳороти мушкилот

Бо назардошти пурра Дарахти ҷустуҷӯи бинарӣ, алгоритми ба а табдил додани онро нависед Хӯчаҳои мин, ки барои табдил додани BST ба Min Heap. Тӯфони Min бояд тавре бошад, ки арзишҳои чапи гиреҳ бояд аз арзишҳои рости гиреҳ камтар бошанд.

мисол

вуруди

Табдил додан 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) вақтро талаб мекунанд.

Мураккабии фазо = О (Н)

Дар ин ҷо мо n элементро нигоҳ медорем, бинобар ин ҳалли фазоии мураккабии фазоӣ /.
ки N - миқдори умумии гиреҳҳо дар дарахти ҷустуҷӯи бинарӣ.

Шарҳ

Дарахтро, ки дар мисоли боло нишон дода шудааст, дида мебароем.

1 қадами
Дарахтро бо тартиби муқаррарӣ убур кунед ва онро дар қатор нигоҳ доред.
arr [] = {6, 7, 9, 12, 13, 18, 23}

Қадами 2 & 3
Дарахтро дар шакли пешакӣ убур кунед ва арзиши ҳар як гиреҳро бо арзиши мувофиқи дар массив ҷойгиршуда иваз кунед.

Табдил додан BST ба 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