Берілген ата-аналар массивінің екілік ағашын тұрғызыңыз


Күрделілік дәрежесі орта
Жиі кіреді Amazon Microsoft Шапшаң
Array Екілік ағаш ағаш

Берілген ата-аналар массивінен екілік ағаш құру »мәселесі сізге массив берілгенін айтады. Бұл енгізу жиымы екілік ағашты білдіреді. Енді осы енгізу жиымының негізінде екілік ағаш салу керек. Массив ата-аналық түйін индексін әр индексте сақтайды.

мысал

Берілген ата-аналар массивінің екілік ағашын тұрғызыңыз

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), өйткені біз түйіннің құрылғанын немесе жасалмағанын тексеру үшін түйіндер жиымын жасадық. Сонымен, ғарыштық қиындықтар да сызықтық болып табылады.