សាងសង់មែកធាងគោលពីរពីការបង្ហាញតំណាងអារេមាតា


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon ក្រុមហ៊ុន Microsoft Snapdeal
អារេ មែកធាងគោលពីរ មែកធាង

បញ្ហា“ សាងសង់មែកធាងគោលពីរពីការតំណាងអារេមាត្រដ្ឋានដែលបានផ្តល់ឱ្យ” ចែងថាអ្នកត្រូវបានផ្តល់អារេមួយ។ អារេបញ្ចូលនេះតំណាងឱ្យដើមឈើគោលពីរ។ ឥឡូវអ្នកត្រូវសាងសង់មែកធាងគោលពីរនៅលើមូលដ្ឋាននៃអារេបញ្ចូលនេះ។ អារេរក្សាទុកសន្ទស្សន៍នៃថ្នាំងមេនៅសន្ទស្សន៍នីមួយៗ។

ឧទាហរណ៍

សាងសង់មែកធាងគោលពីរពីការបង្ហាញតំណាងអារេមាតា

Inorder Traversal: 3 1 0 4 2 5

វិធីសាស្រ្ត

បញ្ហាស្នើឱ្យយើងសាងសង់មែកធាងគោលពីរពីមេដែលបានផ្តល់ឱ្យ អារេ តំណាង។ អារេមេមួយរក្សាទុកសន្ទស្សន៍នៃថ្នាំងមេនៅសន្ទស្សន៍នីមួយៗនៃអារេ។ ឥឡូវអ្នកត្រូវសាងសង់មែកធាងគោលពីរដោយប្រើអារេនេះ។ តម្លៃ -1 នៅក្នុងអារេបញ្ចូលបង្ហាញពីថ្នាំងជា root នៅក្នុងឯកសារ ដើមឈើ.

វិធីឆោតល្ងង់គឺត្រូវបន្តបង្កើតថ្នាំងថ្មី។ នៅពេលយើងបង្កើតថ្នាំងទាំងនេះយើងតែងតែបង្កើតថ្នាំងតាមលំដាប់នៃកំរិតរបស់វានៅក្នុងមែកធាងគោលពីរ។ ឧទាហរណ៍ដំបូងយើងបង្កើតជាឫសគល់បន្ទាប់មកកូនចៅរបស់វាជាដើម។ បន្ទាប់មកនៅពេលយើងបង្កើតថ្នាំងយើងភ្ជាប់ថ្នាំងនៅក្នុងមែកធាងដោយមានជំនួយពីការកែប្រែចំណុច។ ប៉ុន្តែវិធីសាស្រ្តនេះមិនមានប្រសិទ្ធភាពទេព្រោះយើងនឹងឆ្លងកាត់ដើមឈើដើម្បីរកមេនៃថ្នាំងដែលបានបង្កើតបច្ចុប្បន្ន។

ដំណោះស្រាយល្អប្រសើរនិងមានប្រសិទ្ធភាពគឺត្រូវតាមដានថ្នាំងដែលបានបង្កើតរួចហើយ។ វិធីនេះយើងមិនចាំបាច់ស្វែងរកមេនៃថ្នាំងបច្ចុប្បន្នទេ។ ដំណោះស្រាយនេះគឺខុសគ្នាបន្តិចបន្តួច។ ដំបូងយើងនឹងពិនិត្យមើលប្រសិនបើថ្នាំងមេត្រូវបានបង្កើត។ ប្រសិនបើវាត្រូវបានបង្កើតបន្ទាប់មកវាមិនអីទេ។ បើមិនដូច្នោះទេយើងបង្កើតថ្នាំងមេម្តងហើយម្តងទៀតបន្ទាប់មកបង្កើតថ្នាំងកុមារ។ វិធីនេះយើងបន្តភ្ជាប់ថ្នាំងកុមារជាមួយនឹងការកែប្រែទ្រនិច។

លេខកូដ

កូដ 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), ពីព្រោះយើងបានបង្កើតថ្នាំងជាច្រើនដើម្បីពិនិត្យមើលថាតើថ្នាំងត្រូវបានបង្កើតរឺអត់។ ដូច្នេះភាពស្មុគស្មាញនៃលំហរក៏ជាលីនេអ៊ែរដែរ។