Рекурсивная функция для построения дерева

[Neznayka]

Всем привет.

Нужна функция, которая преобразует этот массив:

[
	{
		id: 1,
		name: 'один',
		parentId: null
	},
	{
		id: 2.
		name: 'два',
		parentId: 1
	},
	{
		id: 3,
		name: 'три',
		parentId: 2
	},
	{
		id: 4,
		name: 'четыре',
		parentId: 2
	},
	{
		id: 5,
		name: 'пять',
		parentId: null
	},
	{
		id: 6,
		name: 'шесть',
		parentId: 5
	},
	{
		id: 7,
		name: 'семь',
		parentId: null
	}
]

в такую структуру:

[
	{
		id: 1,
		name: 'один',
		parentId: null,
		children: [
			{
				id: 2,
				name: 'два',
				parentId: 1,
				children: [
					{
						id: 3,
						name: 'три',
						parentId: 2
					},
					{
						id: 4,
						name: 'четыре',
						parentId: 2
					}
					
				]
			}
			 	
		]
	},
	{
		id: 5,
		name: 'пять',
		parentId: null,
		children: [
			{
				id: 6,
				name: 'шесть',
				parentId: 5
			}
		]
	},
	{
		id: 7,
		name: 'семь',
		parentId: null
	}
]

на PHP представляю как реализовать такую функцию, на JS не получается чего-то.

Помогите пожалуйста

[рони]

Neznayka,
https://javascript.ru/forum/misc/607...tml#post404041

[Alexandroppolus]

1) Предполагаем, что чилд может появиться в массиве раньше своего парента
2) Дерево состоит из тех же объектов, которые лежат в массиве, некоторые из них модифицируются. Если надо делать копию, то в строке 5 заменить arr[i] на создание копии arr[i]

function createTree(arr) {
  if (!arr || !arr.length) { return []; }
  var tree = [], map = new Map();
  for (var i = 0, len = arr.length; i < len; ++i) {
    var item = arr[i];
    var mapItem = map.get(item.id);
    if (!mapItem || Array.isArray(mapItem)) {
      if (mapItem) {
        item.children = mapItem;
      }
      map.set(item.id, item);
    }
    if (item.parentId == null) {
      tree.push(item);
    } else {
      var parentItem = map.get(item.parentId);
      if (!parentItem) {
        map.set(item.parentId, [item]);
      } else {
        var children = Array.isArray(parentItem) ?
          parentItem :
          (parentItem.children = parentItem.children || []);
        children.push(item);
      }
    }
  }
  return tree;
}

[Neznayka]

Извиняюсь, пришлось срочно уехать, только вернулся в тему.

Большое спасибо всем, особенно Alexandroppolus, помогли!

[Malleys]

Ещё вариант...

function createTree(array = []) {
	var map = new Map();

	for(const item of array)
		if(map.has(item.parentId))
			map.get(item.parentId).push(item);
		else
			map.set(item.parentId, [item]);

	for(const [parentId, items] of map)
		for(const item of items)
			if(map.has(item.id))
				item.children = map.get(item.id);

	return map.get(null);
}

В исходном массиве элементы могут идти в любом порядке!

[Alexandroppolus]

Мой всё равно более компактный и с рекурсией, как просили.

рекурсия тут нахрен не нужна.

а варианты лучше по скорости выполнения сравнивать, на большом массиве. Я не сравнивал, но асимптотика твоего варианта - O(N^2), а у способов с картой - O(N) или O(N*ln(N)), смотря как там карта устроена

[Malleys]

Мой всё равно более компактный и с рекурсией, как просили.

Если ваша компактность измеряется в количестве переводов строк, то я могу сделать более компактней...

function createTree(array = []) {
	var map = new Map();
	for(const item of array) if(map.has(item.parentId)) map.get(item.parentId).push(item); else map.set(item.parentId, [item]);
	for(const [parentId, items] of map) for(const item of items) if(map.has(item.id)) item.children = map.get(item.id);
	return map.get(null);
}

И тут уже есть определение функции createTree! А у вас его нет! Так где же ваша компактность, когда на каждый массив придётся писать...

const Новый_массив = Массив.filter(зн => зн.parentId === null).map(зн => Найти_выродков(Массив, зн));

против более компактного

createTree(Массив);

от Alexandroppolus!

и с рекурсией

Это предположение того, как, может быть, решается! Вы вправе предоставить более эффективный способ!