Как правильно обойти объект JS для построения дерева?

Question

[Кирилл Горлов]

Есть массив:

const categories = [
  { id: 1, name: 'name 1', parent: null },
  { id: 2, name: 'name 2', parent: 1 },
  { id: 3, name: 'name 3', parent: 6 },
  { id: 4, name: 'name 4', parent: 5 },
  { id: 5, name: 'name 5', parent: 6 },
  { id: 6, name: 'name 6', parent: null },
  { id: 7, name: 'name 7', parent: null }
]

Как правильно описать функцию чтобы на выходе получилось следующее:

const categories = [
  { id: 1, name: 'name 1', parent: null, childrens: [
  	{ id: 2, name: 'name 2', parent: 1 }
  ] },
  { id: 6, name: 'name 6', parent: null, childrens: [
    { id: 3, name: 'name 3', parent: 6 },
    { id: 5, name: 'name 5', parent: 6, childrens: [
      { id: 4, name: 'name 4', parent: 5 }
    ] },
  ] },
  { id: 7, name: 'name 7', parent: null }
]

Answer 1

[Negwereth]

Составление дерева любого уровня вложенности.

const categories = [
  { id: 1, name: 'name 1', parent: null },
  { id: 2, name: 'name 2', parent: 1 },
  { id: 3, name: 'name 3', parent: 6 },
  { id: 4, name: 'name 4', parent: 5 },
  { id: 5, name: 'name 5', parent: 6 },
  { id: 6, name: 'name 6', parent: null },
  { id: 7, name: 'name 7', parent: null }
]

function buildTree (array) {
  // Складываем все элементы будущего дерева в мап под id-ключами
  // Так легче делать поиск родительской ноды
  const map = new Map(categories.map(item => [item.id, item]));
  
  // Обход в цикле по значениям, хранящимся в мапе
  for (let item of map.values()) {
    
    // Проверка, является ли нода дочерней (при parent === null вернет undefined)
    if (!map.has(item.parent)) {
      continue;
    }
    
    // Сохраняем прямую ссылку на родительскую ноду, чтобы дважды не доставать из мапа
    const parent = map.get(item.parent);

    // Добавляем поточную ноду в список дочерних нод родительчкого узла.
    // Здесь сокращено записана проверка на то, есть ли у ноды свойство children.
    parent.children = [...parent.children || [], item];
  }

  // Возвращаем верхний уровень дерева. Все дочерние узлы уже есть в нужных родительских нодах
  return [...map.values()].filter(item => !item.parent);
}

const tree = buildTree(categories);

console.log(tree);

Answer 2

[Anton Mashletov]

const categories = [
    { id: 1, name: 'name 1', parent: null },
    { id: 2, name: 'name 2', parent: 1 },
    { id: 3, name: 'name 3', parent: 6 },
    { id: 4, name: 'name 4', parent: 5 },
    { id: 5, name: 'name 5', parent: 6 },
    { id: 6, name: 'name 6', parent: null },
    { id: 7, name: 'name 7', parent: null }
];

function buildTree(items, parent) {
    parent = parent || null;
    let result = [];

    items.forEach((item) => {
        if (item.parent === parent) {
            result.push(item);
            item.children = buildTree(items, item.id);

            if (!item.children.length) {
                delete item.children;
            }
        }
    });
    
    return result;
}
// todo: не обходить уже добавленные
console.log(buildTree(categories));

Answer 3

[ivanovSP]

Как построить дерево на основе parent?