بائنری ٹری تعمیر شدہ والدین کی نمائندگی سے بنائیں


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایمیزون مائیکروسافٹ Snapdeal
لڑی ثنائی درخت درخت

"دیئے جانے والے والدین کی نمائندگی سے بائنری ٹری تعمیر کرو" مسئلہ یہ بتاتا ہے کہ آپ کو ایک صف دی جاتی ہے۔ یہ ان پٹ سرنی بائنری ٹری کی نمائندگی کرتی ہے۔ اب آپ کو اس ان پٹ سرنی کی بنیاد پر بائنری ٹری تعمیر کرنے کی ضرورت ہے۔ سرنی ہر انڈیکس میں پیرنٹ نوڈ کا انڈیکس اسٹور کرتی ہے۔

مثال کے طور پر

بائنری ٹری تعمیر شدہ والدین کی نمائندگی سے بنائیں

Inorder Traversal: 3 1 0 4 2 5

نقطہ نظر

مسئلہ ہمیں والدین سے بائنری ٹری تعمیر کرنے کا مطالبہ کرتا ہے صف نمائندگی. والدین کے سرنی سرے کے ہر اشاریے میں پیرنٹ نوڈ کا اشاریہ جمع کرتا ہے۔ اب آپ کو اس صف کا استعمال کرتے ہوئے بائنری ٹری تعمیر کرنے کی ضرورت ہے۔ ان پٹ سرنی میں قدر -1 ، میں جڑ نوڈ کی نشاندہی کرتی ہے درخت.

نیا نوڈس تخلیق کرتے رہنا ایک بولی انداز ہے۔ جب ہم یہ نوڈس بناتے ہیں تو ہم ہمیشہ بائنری ٹری میں ان کی سطح کے مطابق نوڈس تیار کرتے ہیں۔ مثال کے طور پر ، پہلے ہم جڑ بناتے ہیں پھر اس کے بچے وغیرہ۔ اس کے بعد جب ہم نوڈس تیار کرتے ہیں تو ہم پوائنٹرز ترمیم کی مدد سے درخت میں نوڈس جوڑ دیتے ہیں۔ لیکن یہ نقطہ نظر موثر نہیں ہے کیونکہ ہم اس وقت پیدا ہونے والے نوڈ کے والدین کو تلاش کرنے کے لئے درخت سے گزر رہے ہیں۔

ایک بہتر اور موثر حل یہ ہے کہ پہلے سے بنائے گئے نوڈس کو ٹریک کرلیں۔ اس طرح ہمیں موجودہ نوڈ کے والدین کو تلاش کرنے کی ضرورت نہیں ہے۔ یہ حل کچھ مختلف ہے۔ یہاں ہم پہلے جائزہ لیں گے کہ پیرنٹ نوڈ تخلیق ہوا ہے یا نہیں۔ اگر یہ بنا ہے تو ٹھیک ہے۔ بصورت دیگر ، ہم بار بار والدین کے تمام نوڈس تخلیق کرتے ہیں اور پھر چائلڈ نوڈ بناتے ہیں۔ اس طرح ہم پوائنٹر میں ترمیم کے ساتھ چلڈرن نوڈس کو بھی جوڑتے رہتے ہیں۔

ضابطے

بائنری ٹری کی تعمیر کے لئے C ++ کوڈ جس میں والدین کی نمائندگی کی گئی ہے

#include<bits/stdc++.h>
using namespace std;

struct node {
  int data;
  node *left, *right;
};

node* create(int data){
  node* tmp = new node();
  tmp->data = data;
  tmp->left = tmp->right = NULL;
  return tmp;
}

void inorder(node* root){
    if(root){
        inorder(root->left);
        cout<<root->data<<" ";
        inorder(root->right);
    }
}

void createNode(int a[], int i, node* created[]){
    // if current node is root
    if(a[i] == -1){
        node* cur = new node();
        cur->data = i;
        created[i] = cur;
        return;
    }

    // if the parent node has not been created
    if(created[a[i]] == NULL)
        createNode(a, a[i], created);

    // create current node
    node* cur = new node();
    cur->data = i;
    // insert the node value in created array
    created[i] = cur;

    // if left child of parent is null
    // attach current node as its left child
    if(created[a[i]]->left == NULL)
        created[a[i]]->left = cur;
    // else attach it as right child
    else if(created[a[i]]->right == NULL)
        created[a[i]]->right = cur;
}

int main()
{
  int a[] = {-1, 0, 0, 1, 2, 2};
  int n = (sizeof a) / (sizeof a[0]);
  node* created[n];
  memset(created, NULL, sizeof created);
  node* root = NULL;
  for(int i=0;i<n;i++){
        // if node has not been created
        if(created[i] == NULL)
            createNode(a, i, created);
        // store the root node
        if(a[i] == -1)
            root = created[i];
  }
  // print the inorder traversal of the root
  inorder(root);
}
3 1 0 4 2 5

جاوا کوڈ بائنری ٹری کی تعمیر کے لئے دیئے گئے والدین کی نمائندگی سے

import java.util.*;

class node{
  int data;
  node left, right;
}

class Main{

  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = tmp.right = null;
    return tmp;
  }

  static void inorder(node root){
      if(root != null){
          inorder(root.left);
          System.out.print(root.data+" ");
          inorder(root.right);
      }
  }

  static void createNode(int a[], int i, node created[]){
      // if current node is root
      if(a[i] == -1){
          node cur = new node();
          cur.data = i;
          created[i] = cur;
          return;
      }

      // if the parent node has not been created
      if(created[a[i]] == null)
          createNode(a, a[i], created);

      // create current node
      node cur = new node();
      cur.data = i;
      // insert the node value in created array
      created[i] = cur;

      // if left child of parent is null
      // attach current node as its left child
      if(created[a[i]].left == null)
          created[a[i]].left = cur;
      // else attach it as right child
      else if(created[a[i]].right == null)
          created[a[i]].right = cur;
  }

  public static void main(String[] args)
  {
    int a[] = {-1, 0, 0, 1, 2, 2};
    int n = 6;
    node created[] = new node[n];
    node root = null;
    for(int i=0;i<n;i++){
          // if node has not been created
          if(created[i] == null)
              createNode(a, i, created);
          // store the root node
          if(a[i] == -1)
              root = created[i];
    }
    // print the inorder traversal of the root
    inorder(root);
  }
}
3 1 0 4 2 5

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (N) ، کیونکہ اگرچہ ہم تکرار استعمال کررہے ہیں۔ اگر نوڈ بنتا ہے تو ہم پھر کبھی وہی نوڈ نہیں بناتے ہیں۔ اس طرح وقت کی حد خطوط ہے۔

خلائی پیچیدگی

O (N) ، کیونکہ ہم نے یہ نوڈس بنانے کے لئے نوڈس کا ایک صف تیار کیا ہے کہ آیا نوڈ تخلیق ہوا ہے یا نہیں۔ اس طرح خلائی پیچیدگی بھی لکیری ہوتی ہے۔