Конвертиране на BST в Min Heap  


Ниво на трудност Трудно
Често задавани в Амазонка 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) време.

Вижте също
Намерете дублирани поддървета

Сложност на пространството = НА)

Тук съхраняваме 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