Как вы освобождаете массив узлов от пути дерева маршрутизации?

Question

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

const nodes = [
  {
    "id": "1",
    "path": "/home",
  },
  {
    "id": "2",
    "path": "/users",
  },
  {
    "id": "3",
    "path": "/users/alice",
  },
  {
    "id": "4",
    "path": "/users/bob",
  },
  {
    "id": "5",
    "path": "/users/alice/posts",
  }
];

Для преобразования массива в следующий вложенный объект:

{
  "path": "/",
  "children": [
    {
      "id": "1",
      "path": "/home",
      "children": []
    },
    {
      "id": "2",
      "path": "/users",
      "children": [
        {
          "id": "3",
          "path": "/users/alice",
          "children": [
            {
              "children": [],
              "id": "5",
              "path": "/users/alice/posts"
            }
          ]
        },
        {
          "id": "4",
          "path": "/users/bob",
          "children": []
        }
      ]
    }
  ]
}

Answer 1

Это моё решение. То, что я сделал:

• Сначала создайте дерево только с каталогом root (т.е. path: '/')
• Затем для каждого узла я "прохожу" его в соответствии с к его path
• я перейду каждый каталог, разделенный / в каждом узле. Затем я проверю, существует ли уже поддерево (т.е. children) в массиве children указанного каталога. Если его нет, создайте новое поддерево и добавьте его в массив.
• Для каждого каталога, пройденного в узле, обновите переменную traversed, чтобы сохранить текущее пройденное поддерево
• Когда я достигаю конечного каталога каждого узла, обновите идентификатор каталога до идентификатора узла

Вот рабочий пример (код ниже работает, когда paths не отсортированы, то есть некоторые более длинные пути с каталогами, которые не существуют, создайте указанные каталоги):

const nodes = [{ "id": "1", "path": "/home" }, { "id": "2", "path": "/users" }, { "id": "3", "path": "/users/alice" }, { "id": "4", "path": "/users/bob" }, { "id": "5", "path": "/users/alice/posts" }]
const tree = { path: '/', children:[] }

nodes.forEach(node => {
  const dirs = node.path.split('/').slice(1)
  let traversed = tree // Hold the reference of tree
  let totalPath = ``
  
  dirs.forEach((dir, index) => {
    const foundChild = traversed.children.find(child => child.path === `${totalPath}/${dir}`)
    const currSubtree = foundChild ? foundChild : { path: `${totalPath}/${dir}`, children: [] }
    
    if (!foundChild) traversed.children.push(currSubtree)
    if (index === dirs.length - 1) currSubtree.id = node.id
    traversed = currSubtree
    totalPath += `/${dir}`
  })
})

console.log(tree)

Answer 2

Поскольку в предыдущих ответах не указан полный путь для каждого вложенного узла (и я считаю, что это именно то, чего хочет OP), вот мое мнение:

• сортировка объектов по длине пути и их идентификатору
• для каждого объекта разделить его путь
• для каждого каталога разделенного пути попытаться найти объект в дереве, который соответствует частичному пути
• .reduce() вернет последний объект, который совпал (или наше начальное значение, которое является основой дерева)
• pu sh начальный объект в этом

const nodes = [
  {"id": "4","path": "/users/bob"},
  {"id": "5","path": "/users/alice/posts"},
  {"id":"6", "path": "/home/somedir/etc"},
  {"id": "2","path": "/users"},
  {"id": "1", "path": "/home"},
  {"id": "3","path": "/users/alice"}
];
const tree = {path: "/", children: []};

nodes.sort((a, b) => (a.path.split('/').length - b.path.split('/').length) || parseInt(a.id) - parseInt(b.id))
  .forEach(node => node.path.split('/').slice(1)
  .reduce(((a, b) => (a.children.find(el => el.path.slice(el.path.lastIndexOf('/') + 1) === b) || a)), tree)
  .children.push({id: node.id, path: node.path, children: []}));

console.log(tree);

Стоит отметить, что этот код не создает промежуточные узлы / пути, если они не были предоставлены, то есть /home/somedir/etc будет вложено в /home, поскольку /home/somedir не существует в исходном массиве.

Answer 3

Пожалуйста, посмотрите здесь:

    const nodes = [ { "id": "1", "path": "/home",},{"id": "2","path": "/users",},{"id": "3","path": "/users/alice",},{"id": "4","path": "/users/bob",},{"id": "5","path": "/users/alice/posts",}];
    const tree = {path: "/", children: []};
    nodes.map(t => ({id: t.id, path: t.path.split('/').slice(1)}))
        .sort((a, b) => a.path.length - b.path.length)
        .forEach(t => {
            t.path.slice(0, -1).reduce((a, b) => a.children.find(el => el.path === b), tree).children.push({
                id: t.id,
                path: t.path[t.path.length - 1],
                children: []
            });
        });
    console.log(tree);