Алгоритм преобразования линейного массива в многомерный и наоборот

[Shitbox2]

Посоветуйте быстрый алгоритм, который из такого массива:

[
    {id: 1, pid: null},
    {id: 2, pid: null},
    {id: 3, pid: 5},
    {id: 4, pid: 5},
    {id: 5, pid: 2}
]

сделает такой:

[
    {id: 1, child: []},
    {id: 2, child:
        [
            {id: 5, child:
                [
                    {id: 4, child: []},
                    {id: 3, child: []}
                ]
            }
        ]
    }
]

и наоборот

[animhotep]

так этож разные масивы, где между ними связь?

[Shitbox2]

так этож разные масивы, где между ними связь?

pid — это идентификатор родителя. Так что зависимости они создают одни и те же

[oneguy]

Вот преобразование в обе стороны.

//преобразование с 1-го представления во 2-ой
function trans(arr) {
  var b=[], res=[];
  for (var i=0; i<arr.length; i++)
    b[arr[i].id]={
      id: arr[i].id,
      child: []
    };
  for (i=0; i<arr.length; i++) {
    if (arr[i].pid==null)
      res.push(b[arr[i].id]);
    else b[arr[i].pid].child.push(b[arr[i].id]);
  }
  return res;
}
/*обратное преобразование, используется рекурсия.
Предполагается, что структура является деревом (не циклическая)*/
function revTrans(arr) {
  var res=[];
  (function _revTrans(arr, pid) {
    for (var i=0; i<arr.length; i++) {
      res.push({
        id: arr[i].id,
        pid: pid
      });
      _revTrans(arr[i].child, arr[i].id);
    }
  })(arr, null);
  return res;
}
//тест
var arr=[
    {id: 1, pid: null},
    {id: 2, pid: null},
    {id: 3, pid: 5},
    {id: 4, pid: 5},
    {id: 5, pid: 2}
];
var arr2=trans(arr);
alert(JSON.stringify(arr2, undefined, 2));
alert(JSON.stringify(revTrans(arr2), undefined, 2));

[Shitbox2]

Спасибо! Я, кстати, в первом случае рекурсией делал. Интересно, можно второй способ итерациями сделать?

[oneguy]

Спасибо! Я, кстати, в первом случае рекурсией делал. Интересно, можно второй способ итерациями сделать?

Можно, но это не будет намного эффективнее.

[PeaceCoder]

Можно, но это не будет намного эффективнее.

В случае глубокой рекурсии будет

http://learn.javascript.ru/memory-ma...81%D1%82%D1%8C