Как преобразовать структуру в иерархическую?

#javascript #json

Как преобразовать плоскую структуру в виде дерева где есть id и parent_id.
В иерархическую вложенную?

Исходная:

[{
  id: 1
},{
  id: 3,
  parent_id: 1
},
{
  id: 4,
  parent_id: 3
},{
  id: 5,
  parent_id: 3
},{
  id: 6,
  parent_id: 1
}]


В иерархическую

[{
  id:1,
  children: [
  {
    id: 3,
    children: [{
      id: 4
    },{
      id: 5
    }]
  },
  {
    id: 6
  }]
}]




Готовый алгоритм:

/**
 * Преобразование плоской структуры в иерархическую
 * @param  {Array} flat плоский массив где есть свойства id и parentId
 * @return {JSON}      иерархический массив со свойствами children
 */
    function flatToHierarchy(flat) {
      const roots = [];
      const all = {};
      flat.forEach((item) => {
        all[item.id] = item;
      });
      Object.keys(all).forEach((id) => {
        const item = all[id];
        if (item.parentId === null || (!item.parentId)) {
          roots.push(item);
        } else if (item.parentId in all) {
          const p = all[item.parentId];
          if (!('children' in p)) {
            p.children = [];
          }
          p.children.push(item);
        }
      });
      return roots;
    }

const Harray = flatToHierarchy(array)

    

Ответы

Ответ 1

Может так



var arrFlat = [
    { id: 1 },
    { id: 3, parent_id: 1 },
    { id: 4, parent_id: 3 },
    { id: 5, parent_id: 3 },
    { id: 6, parent_id: 1 },
    { id: 7, parent_id: 6 },
    { id: 8, parent_id: 7 },
    { id: 9, parent_id: null },
    { id: 10, parent_id: 123 } // типа нет такого родителя
];

function flatToHierarchy ( flat ) {
    const roots = [ ],
            map = [ ],
            id = [ ];
    flat.forEach( item => {
        map.push( Object.assign( { }, item ) ); // копируем
        id.push( item.id );
    } );
    let i;
    map.forEach( item => {
        // Не пойму зачем вы вставили сюда null !?
        if ( /*item.parent_id === null ||*/ !item.parent_id || ( i = id.indexOf(
item.parent_id ) ) === -1 ) {
            roots.push( item );
            return;
        }
        if ( map[i].children ) {
            map[i].children.push( item );
        }
        else {
            map[i].children = [ item ];
        }
    } );
    return roots;
}

console.log( JSON.stringify( flatToHierarchy( arrFlat ), null, 2 ) );


Ответ 2

Такой ответ интересует? Вроде выглядит правильно, насколько могу судить, но меня
смущает, что в вашем примере в выводе у вложенных элементов отсутствуют parent_id.
Я их не убираю в своем ответе, но, если что, можно этот момент пересмотреть.



let source = [{
    id: 1
  }, {
    id: 3,
    parent_id: 1
  },
  {
    id: 4,
    parent_id: 3
  }, {
    id: 5,
    parent_id: 3
  }, {
    id: 6,
    parent_id: 1
  }
];

let res = source.reduce((acc, curr, index, orig) => {
  if (curr.parent_id) {
    let parent = orig.find(item => {
      return item.id === curr.parent_id;
    });

    (parent.children = parent.children || []).push(curr);
    return acc;
  } else {
    acc.push(curr);
    return acc;
  }
}, []);

console.log(res);




По факту основная трудность в подобных задачах (по крайней мере лично для меня) заключается
в том, чтобы в верхний уровень результирующего массива попали только некоторые элементы
исходного массива. Проблема, очевидно, в том, что большинство методов (map, forEach
и т.п.) не позволяют без костылей менять длину входного массива, а, как известно, тряски
со splice внутри циклов обычно ничем хорошим не заканчиваются.

Собственно, отсюда было принято решение использовать reduce, поскольку это один из
немногих способов (с более или менее читаемым кодом на выходе), который позволяет обработать
входной массив таким образом, что на выходе будет любое другое значение (даже, вероятно,
другого типа). В данном случае - совершенно новый массив, в который попадут только
некоторые элементы исходного.

Суть работы моего примера в том, чтобы на каждой итерации найти в оригинальном массиве
родительский элемент для текущего элемента и поместить его в children родителя; при
этом, если родительского элемента для текущего элемента не существует, то его (сам
элемент) нужно просто поместить прямо в результирующий массив.

Очевидно, из-за поиска внутри reduce сложность алгоритма хромает, и, насколько я
могу судить (а тут я не силён), примерно равна O(n^2) (что довольно печально).