בנה עץ בינארי מייצוג מערך הורים נתון  


רמת קושי בינוני
נשאל לעתים קרובות אמזון בעברית מיקרוסופט Snapdeal
מערך עץ בינארי עֵץ

הבעיה "בנה עץ בינארי מייצוג מערך הורים נתון" קובעת שקיבלת מערך. מערך קלט זה מייצג עץ בינארי. כעת עליך לבנות עץ בינארי על בסיס מערך קלט זה. המערך מאחסן את האינדקס של צומת האב בכל אינדקס.

דוגמה  

בנה עץ בינארי מייצוג מערך הורים נתוןאורן

Inorder Traversal: 3 1 0 4 2 5

גישה  

הבעיה מבקשת מאיתנו לבנות עץ בינארי מההורה הנתון מערך יִצוּג. מערך אב מאחסן את האינדקס של צומת האב בכל אינדקס של המערך. כעת עליך לבנות עץ בינארי באמצעות מערך זה. הערך -1 במערך הקלט מציין את צומת השורש ב- עץ.

גישה נאיבית היא להמשיך ליצור צמתים חדשים. כשאנחנו יוצרים את הצמתים האלה אנחנו תמיד יוצרים את הצמתים לפי סדר הרמה שלהם בעץ הבינארי. לדוגמה, ראשית, אנו יוצרים שורש ואז ילדיו וכו '. ואז כשאנחנו יוצרים את הצמתים אנו מצמידים את הצמתים בעץ בעזרת שינוי מצביעים. אך גישה זו אינה יעילה מכיוון שנעבור את העץ כדי למצוא את האב של הצומת שנוצר כרגע.

פתרון טוב ויעיל יותר הוא לעקוב אחר הצמתים שכבר נוצרו. בדרך זו אנחנו לא צריכים לחפש את ההורה של הצומת הנוכחי. הפיתרון הזה קצת שונה. כאן נבדוק תחילה אם נוצר צומת האב. אם זה נוצר אז זה בסדר. אחרת, אנו יוצרים באופן רקורסיבי את כל צמתי האב ואז יוצרים את צומת הצאצא. בדרך זו אנו ממשיכים לצרף את צמתי הילד עם שינוי המצביע.

ראה גם
פתרון Leetcode לפיתוח

קופונים  

קוד 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) כי יצרנו מערך צמתים כדי לבדוק אם הצומת נוצר או לא. לפיכך מורכבות החלל היא גם לינארית.