بناء شجرة ثنائية من تمثيل مصفوفة أصل معين


مستوى الصعوبة متوسط
كثيرا ما يطلب في أمازون Microsoft 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) لأننا أنشأنا مجموعة من العقد للتحقق مما إذا كانت العقدة قد تم إنشاؤها أم لا. وبالتالي فإن تعقيد الفضاء يكون خطيًا أيضًا.