Javascript.RU

Создать новую тему Ответ
 
Опции темы Искать в теме
  #1 (permalink)  
Старый 18.07.2019, 23:07
Аспирант
Отправить личное сообщение для Neznayka Посмотреть профиль Найти все сообщения от Neznayka
 
Регистрация: 08.03.2013
Сообщений: 37

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

Нужна функция, которая преобразует этот массив:
Код:
[
	{
		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 не получается чего-то.

Помогите пожалуйста
Ответить с цитированием
  #2 (permalink)  
Старый 18.07.2019, 23:49
Аватар для рони
Профессор
Отправить личное сообщение для рони Посмотреть профиль Найти все сообщения от рони
 
Регистрация: 27.05.2010
Сообщений: 33,064

Neznayka,
https://javascript.ru/forum/misc/607...tml#post404041
Ответить с цитированием
  #3 (permalink)  
Старый 19.07.2019, 09:46
Аватар для Alexandroppolus
Профессор
Отправить личное сообщение для Alexandroppolus Посмотреть профиль Найти все сообщения от Alexandroppolus
 
Регистрация: 25.10.2016
Сообщений: 1,004

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;
}
Ответить с цитированием
  #4 (permalink)  
Старый 26.07.2019, 00:42
Аспирант
Отправить личное сообщение для Neznayka Посмотреть профиль Найти все сообщения от Neznayka
 
Регистрация: 08.03.2013
Сообщений: 37

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

Большое спасибо всем, особенно Alexandroppolus, помогли!
Ответить с цитированием
  #5 (permalink)  
Старый 26.07.2019, 02:05
Аватар для Malleys
Профессор
Отправить личное сообщение для Malleys Посмотреть профиль Найти все сообщения от Malleys
 
Регистрация: 20.12.2009
Сообщений: 1,714

Ещё вариант...
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);
}


В исходном массиве элементы могут идти в любом порядке!
Ответить с цитированием
  #6 (permalink)  
Старый 26.07.2019, 10:04
Аватар для Alexandroppolus
Профессор
Отправить личное сообщение для Alexandroppolus Посмотреть профиль Найти все сообщения от Alexandroppolus
 
Регистрация: 25.10.2016
Сообщений: 1,004

Сообщение от Русский
Мой всё равно более компактный и с рекурсией, как просили.
рекурсия тут нахрен не нужна.

а варианты лучше по скорости выполнения сравнивать, на большом массиве. Я не сравнивал, но асимптотика твоего варианта - O(N^2), а у способов с картой - O(N) или O(N*ln(N)), смотря как там карта устроена
Ответить с цитированием
  #7 (permalink)  
Старый 28.07.2019, 07:41
Аватар для Malleys
Профессор
Отправить личное сообщение для Malleys Посмотреть профиль Найти все сообщения от Malleys
 
Регистрация: 20.12.2009
Сообщений: 1,714

Сообщение от Русский
Мой всё равно более компактный и с рекурсией, как просили.
Если ваша компактность измеряется в количестве переводов строк, то я могу сделать более компактней...
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!

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

Последний раз редактировалось Malleys, 28.07.2019 в 07:44.
Ответить с цитированием
Ответ



Опции темы Искать в теме
Искать в теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Функция для сортировки таблицы JStudent Общие вопросы Javascript 19 27.09.2019 12:42
таймер для функция Hovik Общие вопросы Javascript 6 08.11.2018 05:58
Модуль для работы с модулями JSprog Ваши сайты и скрипты 29 02.09.2009 13:31
Переодическое обновление значений для графика, функция для обновления значений yupa87 Общие вопросы Javascript 0 09.07.2009 14:48
Как узнать, завершила ли свою работу рекурсивная функция Ajax Общие вопросы Javascript 4 13.05.2009 14:50