Линейный массив в иерархический

Question

У меня есть данные, поступающие в линейном формате, например:

const data = [
  {
    "id": "1",
    "parentId": null
  },
  {
    "id": "1.1",
    "parentId": "1"
  },
  {
    "id": "1.2",
    "parentId": "1"
  },
  {
    "id": "2",
    "parentId": null
  },
  {
    "id": "2.1",
    "parentId": "2"
  },
  {
    "id": "3",
    "parentId": null
  },
  {
    "id": "3.1",
    "parentId": "3"
  },
  {
    "id": "3.1.1",
    "parentId": "3.1"
  },
  {
    "id": "3.1.1.1",
    "parentId": "3.1.1"
  }
];

Я хочу преобразовать их в иерархический формат, например:

const hierarchicalData = [
  {
    "id": "1",
    "children": [
      {
        "id": "1.1",
      },
      {
        "id": "1.2",
      }
    ]
  },
  ...
]

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

Я занимаюсь этим уже около 3 часов и не могу понять, как это сделать.

Вот пример, демонстрирующий мою проблему:

var output = [];

$.each(data, function(index, value) {
    if (value.parentId === null) {
    value.children = [];
    output.push(value);
  } else {
    $.each(output, function(innerIndex, innerValue) {
        if (value.parentId === innerValue.id) {
        innerValue.children.push(value);
        return;
      }
    });
  }
});

console.log(output);

Answer 1

Вот альтернативный подход, использующий только Vanilla JavaScript.Непосредственно созданный объект o - это еще не совсем то, что вы хотели, но хорошая отправная точка:

{
  "1": {
    "1": {
      "id": "1.1"
    },
    "2": {
      "id": "1.2"
    },
    "id": "1"
  },
  "2": {
    "1": {
      "id": "2.1"
    },
    "id": "2"
  },
  "3": {
    "1": {
      "1": {
        "1": {
          "id": "3.1.1.1"
        },
        "id": "3.1.1"
      },
      "id": "3.1"
    },
    "id": "3"
  }
}

Ваш точный результат тогда легко достижим, если применить рекурсивную функцию mca() (= makeChildArray) кобъект:

const data = [
  {"id": "1","parentId": null},
  {"id": "1.1","parentId": "1"},
  {"id": "1.2","parentId": "1"},
  {"id": "2","parentId": null},
  {"id": "2.1","parentId": "2"},
  {"id": "3","parentId": null},
  {"id": "3.1","parentId": "3"},
  {"id": "3.1.1","parentId": "3.1"},
  {"id": "3.1.1.1","parentId": "3.1.1"}
];

// the "one-liner" to make object o:
var o={};
data.forEach(el=>el.id.split('.').reduce((so,k)=>so[k]=so[k] || {id:el.id}, o));

function mca(co){
 if (typeof co==='object'){
  var ret={},cok=Object.keys(co);
  var ncok=cok.filter(k=>!isNaN(k));
  cok.filter(isNaN).forEach(k=>ret[k]=co[k]);
  if (ncok.length) ret.children=ncok.map(k=>mca(co[k]));
  return ret;
 }
 else return co;
}
console.log(mca(o).children);

Окончательный результат:

[
  {
    "id": "1",
    "children": [
      {
        "id": "1.1"
      },
      {
        "id": "1.2"
      }
    ]
  },
  {
    "id": "2",
    "children": [
      {
        "id": "2.1"
      }
    ]
  },
  {
    "id": "3",
    "children": [
      {
        "id": "3.1",
        "children": [
          {
            "id": "3.1.1",
            "children": [
              {
                "id": "3.1.1.1"
              }
            ]
          }
        ]
      }
    ]
  }
]