Блог

Мне нужно сгенерировать плоский массив объектов, содержащий всех предков данного объекта, в плоском нормализованном массиве объектов.

Существует множество примеров превращения его во вложенную древовидную структуру, но я не смог найти никакой информации для простого возврата всех предков в плоский массив. Каждый объект в плоском нормализованном массиве имеет идентификатор и родительский идентификатор.

Дан плоский нормализованный массив объектов

 [
  {
    id: 1,
    name: "node 1",
    parentId: null,
  }, {
    id: 2,
    name: "node 2",
    parentId: 1,
  }, {
    id: 3,
    name: "node 3",
    parentId: null,
  }, {
    id: 4,
    name: "node 4",
    parentId: 3,
  }, {
    id: 5,
    name: "node 5",
    parentId: 2,
  }, {
    id: 6,
    name: "node 6",
    parentId: 1,
  }, {
    id: 7,
    name: "node 7",
    parentId: 6,
  },
]
 

При выполнении getAncestors(1) этого должны быть возвращены все предки узла 1

 [
  {
    id: 2,
    name: "node 2",
    parentId: 1,
  }, {
    id: 5,
    name: "node 5",
    parentId: 2,
  }, {
    id: 6,
    name: "node 6",
    parentId: 1,
  }, {
    id: 7,
    name: "node 7",
    parentId: 6,
  },
]
 

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

Для доступа к фаастеру вам нужен файл a Map со всеми узлами и их id ключом as, а также карта для всех родителей с parentId ключом as. Тогда вам нужна функция getAncestors , а внутри вам нужна функция для получения nod и его предков.

Объедините все с уменьшением и верните результат.

 function getAncestors(parentId) {
    const getNode = node => [node, ...getAncestors(node.id)];
    return (parents.get(parentId) || []).reduce((r, id) => [...r, ...getNode(nodes.get(id))], []);
}

var data = [{ id: 1, name: "node 1", parentId: null, }, { id: 2, name: "node 2", parentId: 1 }, { id: 3, name: "node 3", parentId: null }, { id: 4, name: "node 4", parentId: 3 }, { id: 5, name: "node 5", parentId: 2 }, { id: 6, name: "node 6", parentId: 1 }, { id: 7, name: "node 7", parentId: 6 }],
    nodes = new Map(data.map(o => [o.id, o])),
    parents = data.reduce((m, { id, parentId }) => m.set(parentId, [... (m.get(parentId) || []), id]), new Map);

console.log(getAncestors(1)); 

 .as-console-wrapper { max-height: 100% !important; top: 0; }