BST را به Min Heap تبدیل کنید


سطح دشواری سخت
اغلب در آمازون بلک راک ByteDance GE بهداشت و درمان شرکت 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.

پیچیدگی زمان = بر)

از آنجا که ما تراورس درختی را که به ترتیب O و N زمان می برد ، به ترتیب و پیش سفارش انجام می دهیم.

پیچیدگی فضا = بر)

در اینجا ما n عنصر را ذخیره می کنیم ، بنابراین یک راه حل فضایی پیچیدگی فضای خطی /.
جایی که N تعداد کل گره ها در درخت جستجوی دودویی کامل است.

توضیح

درختی که در مثال بالا نشان داده شده را در نظر بگیرید.

1 گام
درخت را به صورت مرتب عبور داده و در یک آرایه ذخیره کنید.
arr [] = {6 ، 7 ، 9 ، 12 ، 13 ، 18 ، 23}

مرحله 2 و 3
درخت را به شکل پیش سفارش عبور داده و مقدار هر گره را با مقدار متناظر ذخیره شده در آرایه جایگزین کنید.

BST را به Min Heap تبدیل کنید

همانطور که در شکل می بینیم ، درخت با جبران خصوصیات داده شده به Min Heap تبدیل می شود.

رمز

جاوا کد برای تبدیل 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