javascript: формирование дерева из списка

Question

подскажите как реализовать следующую задачу (что-то голова вообще не варит с ней уже)

есть массив в котором записаны элементы вида:

у которых есть какой-то родитель:

{name: 'xxx', parent: 'yyy'}

у которых нет родителя (т.е. элементы из корня):

{name: 'xxx', parent: 'yyy'}

требуется сформировать дерево, в котором у родителей будет свойство children представляющее собой массив элементов (включая других родителей, дочерних к указанному)

и вот что-то я застрял на этой задаче единственное как сделал - в лоб, т.е. проходя по элементам и рекурсивно находя сначала элементы для корня, потом элементы для родителей в корне и т.д.

все это приводит к O(n^2) сложности

но можно ли как-то проще это сделать? может Javascript уже предоставляет функционал, позволяющий упростить задачу формирования такого дерева

Пример данных:

[
    {name: 'object1'},
    {name: 'object2', parent: 'object4'},
    {name: 'object3'},
    {name: 'object4', parent: 'object7'},
    {name: 'object5', parent: 'object1'},
    {name: 'object6', parent: 'object4'},
    {name: 'object7'},
]

на выходе должно получиться:

[
    {name: 'object1', children: [
        {name: 'object5'},
    ]},
    {name: 'object3'},
    {name: 'object7', children: [
        {name: 'object4', children: [
            {name: 'object2'},
            {name: 'object6'},
        ]},
    ]},
]

Answer 1

Не знаю, какая тут сложность (алгоритмическая)

const data = [{
    name: "object1"
  },
  {
    name: "object2",
    parent: "object4"
  },
  {
    name: "object3"
  },
  {
    name: "object4",
    parent: "object7"
  },
  {
    name: "object5",
    parent: "object1"
  },
  {
    name: "object6",
    parent: "object4"
  },
  {
    name: "object7"
  },
  {
    name: "object8",
    parent: "object6"
  },
  {
    name: "object9",
    parent: "object8"
  },
];

const result = {};

data.forEach((item) => {
  const key = item.name;
  if (!result[key]) result[key] = {};
  if (result[key]) result[key] = Object.assign(result[key], item);
  if (item.parent) {
    const parentCode = item.parent;
    if (!result[parentCode]) {
      result[parentCode] = {};
    }
    if (!result[parentCode].children) result[parentCode].children = [];
    result[parentCode].children.push(item);
  }
});

Object.keys(result).forEach((key) => {
  const item = result[key];
  if (item.parent && item.children) {
    const index = result[item.parent].children.findIndex((i) => i.name === key);
    result[item.parent].children.splice(index, 1, item);
  }
});

Object.keys(result).forEach(key => {
  if (result[key].parent) delete result[key];
})

console.log(Object.values(result));

Answer 2

let arr = [
    {name: 'object1'},
    {name: 'object2', parent: 'object4'},
    {name: 'object3'},
    {name: 'object4', parent: 'object7'},
    {name: 'object5', parent: 'object1'},
    {name: 'object6', parent: 'object4'},
    {name: 'object7'},
];

let obj = {}; // Вспомогательный словарь для доступа по ключу
arr.forEach( item => obj[item.name] = item );

arr.forEach( item => {
  let parentName = item.parent;
  if( !parentName || !obj[parentName] ) return;
  ( obj[parentName].children ??= [] ).push(item);
});

arr = arr.filter( item => {
  let mustRemove = item.parent;
  delete item.parent;
  return !mustRemove;
});

console.log(arr);

Answer 3

Не знал, как объяснить, пусть будет псевдокодом:

result = [];
helper = {};

Перебирая объекты в исходном массиве:
    В helper уже есть объект с таким же именем?
        Значит это массив children, который оставлен там под этим именем,
        из-за временного отсутствия родителя.
        объект.children = массив

    Добавить объект в helper.

    Если у объекта есть parent:
        Если в helper уже есть такой parent:
            Добавить объект туда.
        Если нет parent:
            helper[имя_родителя] = [объект]
            Будет временным хранилищем для всех children,
            пока перебор не наткнется на родителя, который заберет этот массив себе

Реализация:

let arr = [
  {name: 'object1'},
  {name: 'object2', parent: 'object4'},
  {name: 'object3'},
  {name: 'object4', parent: 'object7'},
  {name: 'object5', parent: 'object1'},
  {name: 'object6', parent: 'object4'},
  {name: 'object7'},
];

let result = [];
let helper = {};

for (let obj of arr) {
  let existing_children = helper[obj.name];
  if (existing_children) {
    obj.children = existing_children;
  }

  helper[obj.name] = obj;

  if (!obj.parent) {
    result.push(obj)
  } else {
  
    let parent = helper[obj.parent]
    if (parent) {
      
      if (parent instanceof Array) {
        parent.push(obj);
      } else {
        (parent.children || (parent.children = [])).push(obj);
      }
      
    } else {
      helper[obj.parent] = [obj];
    }

    delete obj.parent;
  }
  
}

console.log( JSON.stringify(result, 0, 2) );

.as-console-wrapper { min-height: 100vh !important }

Пытался сделать за O(N), вышло много вложенностей, не знаю, как это оценивать)

БЛОГ НА HUSL

javascript: формирование дерева из списка

Ответы (3 шт):