بائنري وڻ کان ثنائي ڳولا لاءِ وڻ جي ionير Conار تي


تڪليف جي سطح آسان
بار بار پڇڻ ۾ ايڊوب Amazon ايپل Bloomberg گوگل Microsoft جي VMware
ثنائي ڳولا وارو وڻ بائنري وڻ گہرائي پهرين ڳولا وڻن وڻ ٽرانسورس

بائنري وڻ ۾ بائنري سرچ وڻ جي تبديلي واري مسئلي ۾ ، اسان هڪ ثنائي وڻ ڏني آهي ان کي Bانچي جي changingانچي کي تبديل ڪرڻ کان سواءِ وڻ.

مثال

پٽ

بائنري وڻ کان ثنائي ڳولا لاءِ وڻ جي ionير Conار تي

پيداوار

بائنري وڻ کان ثنائي ڳولا لاءِ وڻ جي ionير Conار تي

اڳ آرڊر: 13 8 6 47 25 51

الورورٿم

اسان کي بائنري وڻ جي toانچي کي تبديل ڪرڻ ۽ ان کي بائنري سرچ وڻ ۾ تبديل ڪرڻ جي ضرورت ناهي. بائنري سرچ وڻ جي ملڪيت کي نوٽ ڪريو ته انڊرڊر سفر ڪندڙ بائنري سرچ وڻ جي ھڪڙي ترتيب ڏنل ڊيٽا ڏانھن ھلندي آھي. اسان اهو ملڪيت استعمال ڪنداسين مطلوب نتيجا حاصل ڪرڻ لاءِ.

خيال اهو آهي ته بائنري وڻ جي انڊرورس ٽراسل کي هڪ ۾ رکڻ جو صف، صف ترتيب ڏي ۽ پوءِ صف ۽ بائنري وڻ کي ٽوڙيو (انڊرينر فارم ۾) ۽ صف ۾ ساڳيو عنصر سان بائنري وڻ ۾ هر نوڊ بدليو. اھو بئنسري وڻ کي بائنري سرچ وڻ ۾ تبديل ڪندو.

  1. صف ٺاهيو ، آرڊر جو نالو
  2. ترتيب ڏنل فارم ۾ ڏنل بائنري وڻ کي andٽو ڪريو ۽ صف ۾ 'نو آرڊر' ۾ نوڊس جو قدر اسٽور ڪريو.
  3. ترتيب کي ترتيب ڏيو.
  4. ان سان گڏوگڏ آرڊر فارم ۾ صف ۽ بائنري ٽري کي جڙايو ۽ بائنري وڻ ۾ ملندڙ نوڊ جي قيمت کي آرڊر صف ۾ ويليو سان تبديل ڪيو.
  5. ثنائي وڻ کي ثنائي سرچ وڻ ۾ تبديل ڪيو ويندو آهي.

وقت جي پيچيدگي = اي (ن لاگ (اين))
خلائي ڪمپليڪس = اي (ن) ، جيئن اسان آرڊر ٽرورسال کي اسٽور ڪرڻ جي لاءِ استعمال ڪيوسين
جتي ڏنل آهي ثانوي وڻ ۾ نمبر نوڊ جو تعداد.

وضاحت

مٿي ڏنل مثال ۾ ڏيکاريل بائنري وڻ تي غور ڪريو.

قدم 1 ۽ 2

بائنري وڻ جو آرڊر ٽراسيل ترتيب ۾ اسٽور ڪريو.
اندر حڪم [] = {47 ، 51 ، 25 ، 6 ، 13 ، 8}

قدم 3

ترتيب کي ترتيب ڏيو.
اندرڊر = {6 ، 8 ، 13 ، 25 ، 47 ، 51}

قدم 4

ساڳي طرح قطار ۽ بائنري وڻ جو رخ ڪن ۽ ترتيب ڏنل ان آرڊر ترتيب واري ترتيب واري عنصر سان بائنري وڻ جي عنصر کي تبديل ڪريو.
ثنائن جو وڻ ھاڻي ڏسجي ٿو ،

ثنائي وڻ کي ثنائي سرچ وڻ ۾ تبديل ڪيو ويندو آهي.

جاوا ڪوڊ لاءِ بائنري وڻ کان بائنري سرچ وڻ تي

import java.util.ArrayList;
import java.util.Collections;

public class BinaryTreeToBinarySearchTreeConversion {
    // class representing Node of a Binary Tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    // class to provide a wrapper around index
    // so that we can pass it by reference
    static class Index {
        int index;

        public Index(int index) {
            this.index = index;
        }
    }

    // function to print pre order traversal of a binary tree
    private static void preOrder(Node root) {
        if (root != null) {
            System.out.print(root.data + " ");
            preOrder(root.left);
            preOrder(root.right);
        }
    }

    // function to traverse in binary tree in in-order form and store the elements
    // in a list
    private static void inOrderAndFormList(Node root, ArrayList<Integer> inorder) {
        if (root != null) {
            inOrderAndFormList(root.left, inorder);
            // store the current value in the list
            inorder.add(root.data);
            inOrderAndFormList(root.right, inorder);
        }
    }

    // function to traverse in binary tree in in-order form and
    // change the value of elements accordingly
    private static void inOrderAndChange(Node root, ArrayList<Integer> inOrder, Index index) {
        if (root != null) {
            inOrderAndChange(root.left, inOrder, index);
            // change the current element of Tree with current element of list
            root.data = inOrder.get(index.index);
            // increment index by 1
            index.index++;
            inOrderAndChange(root.right, inOrder, index);
        }
    }

    private static void convertToBST(Node root) {
        // create a list and store the inorder of the given Binary Tree
        ArrayList<Integer> inOrder = new ArrayList<>();
        inOrderAndFormList(root, inOrder);

        // Sort the list
        Collections.sort(inOrder);

        // traverse in binary tree and list simultaneously and change the required values
        inOrderAndChange(root, inOrder, new Index(0));
    }

    public static void main(String[] args) {
        // Example Tree
        Node root = new Node(25);
        root.left = new Node(51);
        root.right = new Node(13);
        root.left.left = new Node(47);
        root.right.left = new Node(6);
        root.right.right = new Node(8);

        convertToBST(root);

        preOrder(root);
        System.out.println();
    }
}
13 8 6 47 25 51

بائنري وڻ کان بينري سرچ وڻ جي تبديلي لاءِ سي ++ ڪوڊ

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// class representing Node of a Binary Tree
class Node {
    public:
    int data;
    Node *left;
    Node *right;
    
    Node(int d) {
        data = d;
    }
};

// global variable index
int index = 0;

void preOrder(Node *root) {
    if (root != NULL) {
        cout<<root->data<<" ";
        preOrder(root->left);
        preOrder(root->right);
    }
}

// function to traverse in binary tree in in-order form and store the elements
// in a list
void inOrderAndFormList(Node *root, vector<int> &inOrder) {
    if (root != NULL) {
        inOrderAndFormList(root->left, inOrder);
        // store the current value in the list
        inOrder.push_back(root->data);
        inOrderAndFormList(root->right, inOrder);
    }
}

// function to traverse in binary tree in in-order form and
// change the value of elements accordingly
void inOrderAndChange(Node *root, vector<int>& inOrder) {
    if (root != NULL) {
        inOrderAndChange(root->left, inOrder);
        
        // change the current element of Tree with current element of list
        root->data = inOrder[index];
        index++;
        
        inOrderAndChange(root->right, inOrder);
    }
}

void convertToBST(Node *root) {
    // create a list and store the inorder of the given Binary Tree
    vector<int> inOrder;
    inOrderAndFormList(root, inOrder);

    // Sort the list
    sort(inOrder.begin(), inOrder.end());

    // traverse in binary tree and list simultaneously and change the required values
    index = 0;
    inOrderAndChange(root, inOrder);
}

int main() {
    // Example Tree
    Node *root = new Node(25);
    root->left = new Node(51);
    root->right = new Node(13);
    root->left->left = new Node(47);
    root->right->left = new Node(6);
    root->right->right = new Node(8);

    convertToBST(root);

    preOrder(root);
    cout<<endl;
    
    return 0;
}
13 8 6 47 25 51

حوالا