Берилген Ата-энелер массивинен экилик даракты куруңуз


Кыйынчылык деңгээли орто
Көп суралган Amazon Microsoft Snapdeal
согуштук тизме Binary Tree дарак

"Берилген ата-энелер массивинен экилик даракты куруу" маселеси сизге массив берилгенин билдирет. Бул киргизилген массив экилик даракты билдирет. Эми сиз ушул киргизилген массивдин негизинде экилик даракты курушуңуз керек. Массив ар бир индексте эне түйүнүнүн индексин сактайт.

мисал

Берилген Ата-энелер массивинен экилик даракты куруңуз

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

Берилген Ата-энелер массивинен экилик даракты курууга Java коду

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), анткени биз түйүндүн түзүлгөндүгүн же жоктугун текшерүү үчүн бир катар түйүндөрдү түздүк. Ошентип космостогу татаалдык дагы сызыктуу.