Аз намояндагии массивии волидайн дарахти дуӣ созед


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Amazon Microsoft Snapdeal
тартиботи ҳарбӣ Дарахти дуӣ Дарахт

Масъалаи "Сохтани дарахти дуӣ аз намояндагии массивҳои волидайн" мегӯяд, ки ба шумо массив дода мешавад. Ин массиви вуруд дарахти дутарафаро нишон медиҳад. Акнун ба шумо лозим аст, ки дар асоси ин массиви вуруд дарахти дуӣ бунёд кунед. Массив индекси гиреҳи волидайнро дар ҳар як индекс нигоҳ медорад.

мисол

Аз намояндагии массивии волидайн дарахти дуӣ созед

Inorder Traversal: 3 1 0 4 2 5

усул

Мушкилот аз мо талаб мекунад, ки аз падару модари додашуда дарахти дуӣ созем асал намояндагӣ. Массивҳои волидайн индекси гиреҳи волидайнро дар ҳар як индекси массив нигоҳ медоранд. Акнун ба шумо лозим аст, ки бо истифода аз ин массив дарахти дуӣ бунёд кунед. Қимати -1 дар массиви вуруд гиреҳи решаро дар дарахт.

Усули соддалавҳона ин нигоҳ доштани гиреҳҳои нав мебошад. Вақте ки мо ин гиреҳҳоро месозем, мо ҳамеша гиреҳҳоро бо тартиби дараҷаи онҳо дар дарахти дуӣ месозем. Масалан, аввал, мо реша эҷод мекунем, пас фарзандонаш ва ғайра. пас ҳангоми эҷод кардани гиреҳҳо мо гиреҳҳоро дар дарахт бо ёрии тағирёбии ишоракунандагон замима мекунем. Аммо ин равиш самарабахш нест, зеро мо барои дарёфти волидайни гиреҳи дар айни замон сохташуда аз дарахт мегузарем.

Роҳи беҳтар ва муассир пайгирии пайгирии гиреҳҳоест, ки аллакай сохта шудаанд. Бо ин роҳ мо набояд волидайни гиреҳи кунуниро ҷустуҷӯ кунем. Ин ҳалли каме фарқ мекунад. Дар ин ҷо мо аввал месанҷем, ки гиреҳи волидайн сохта шудааст ё не. Агар он сохта шуда бошад, пас хуб аст. Дар акси ҳол, мо ҳама гиреҳҳои волидайнро рекурсивӣ месозем ва сипас гиреҳи кӯдакро месозем. Ҳамин тавр, мо инчунин пайвастани гиреҳҳои кӯдакро бо тағирёбии нишоннамо идома медиҳем.

рамз

Рамзи C ++ барои сохтани дарахти дуӣ аз намояндагии Array Array

#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

Рамзи Java барои сохтани дарахти дуӣ аз намояндагии Array Array

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), зеро мо массиви гиреҳҳоро сохта будем, ки гиреҳ сохта шудааст ё на. Ҳамин тариқ, мураккабии фазо низ хаттӣ аст.