Как корректно обойти массив для построения дерева?

Question

[Дмитрий Есин]

Необходимо из массива сформировать из вложенную структуру (дерево). Путь для обхода можно взять из поля "name" каждого элемента nodes.

Как определяется вложенность: У каждого элемента есть поле name. Последняя подстрока справа после слэша в этом поле - это title текущего элемента. Далее, чтобы получить родителя или потомков данного элемента, необходимо взять соответственно подстроку слева или подстроку справа от него и таким образом накопить аккумулятор, проходясь по каждому элементу.

У одного элемента в исходной коллекции nodes может быть несколько потомков. Если у элемента потомков нет, то его поле isDirectory === false, в противном случае isDirectory === true.

Исходные данные:

const nodes = [
  {
    "id": 0,
    "name": "\"Корень\"",
    "createDate": "2018-12-11T14:40:26.95",
    "updateDate": "2018-12-11T14:40:26.95",
    "folderId": -1,
    "ctnsCount": 0,
    "ctnsCountDate": "2018-12-11T14:40:26.95",
    "audiences": [0, 0, 0, 0]
  },
  {
    "id": 1000831,
    "name": "\"Store/Сегменты для OPS/Сегменты для внешней рекламы/Автодилеры\"",
    "createDate": "2018-12-29T03:04:28.26",
    "updateDate": "2018-12-29T03:04:28.26",
    "folderId": -1,
    "ctnsCount": 23511,
    "ctnsCountDate": "2019-01-09T05:48:23.487",
    "audiences": []
  },
  {
    "id": 1000249,
    "name": "\"Store/Сегменты для OPS/Сегменты для внешней рекламы\"",
    "createDate": "2018-12-11T14:40:42.313",
    "updateDate": "2018-12-11T14:40:42.313",
    "folderId": -1,
    "ctnsCount": 1490426,
    "ctnsCountDate": "2019-01-09T05:48:04.827",
    "audiences": []
  },
  {
    "id": 1000032,
    "name": "\"Store/Сегменты для OPS\"",
    "createDate": "2018-12-11T14:40:19.48",
    "updateDate": "2018-12-11T14:40:19.48",
    "folderId": -1,
    "ctnsCount": 0,
    "ctnsCountDate": "2018-12-11T14:40:19.48",
    "audiences": []
  },
  {
    "id": 28473,
    "name": "\"Store\"",
    "createDate": "2018-12-11T14:40:32.733",
    "updateDate": "2018-12-11T14:40:32.733",
    "folderId": -1,
    "ctnsCount": 0,
    "ctnsCountDate": "2018-12-11T14:40:32.733",
    "audiences": []
  },
  {
    "id": 1000772,
    "name": "\"Store/Сегменты для OPS/Сегменты для внешней рекламы/Cian\"",
    "createDate": "2018-12-11T14:40:05.02",
    "updateDate": "2018-12-11T14:40:05.02",
    "folderId": -1,
    "ctnsCount": 30409,
    "ctnsCountDate": "2019-01-09T05:48:20.673",
    "audiences": []
  },
  {
    "id": 2681,
    "name": "\"Сегменты Facetz/Образ жизни/Обзоры",
    "createDate": "2018-12-11T14:40:30.623",
    "updateDate": "2018-12-11T14:40:30.623",
    "folderId": -1,
    "ctnsCount": 115379,
    "ctnsCountDate": "2019-01-09T05:48:23.847",
    "audiences": []
  },
  {
    "id": 3840,
    "name": "\"Сегменты Facetz/Образ жизни\"",
    "createDate": "2018-12-11T14:39:46.45",
    "updateDate": "2018-12-11T14:39:46.45",
    "folderId": -1,
    "ctnsCount": 0,
    "ctnsCountDate": "2018-12-11T14:39:46.45",
    "audiences": []
  },
  {
    "id": 3811,
    "name": "\"Сегменты Facetz\"",
    "createDate": "2018-12-11T14:39:46.373",
    "updateDate": "2018-12-11T14:39:46.373",
    "folderId": -1,
    "ctnsCount": 0,
    "ctnsCountDate": "2018-12-11T14:39:46.373",
    "audiences": []
  }
];

Результат:

const result = [
  {
    id: 0,
    title: 'Корень',
    isDirectory: true,
    children: [
      {
        id: 28473,
        title: 'Store',
        isDirectory: true,
        children: [
          {
            id: 1000032,
            title: 'Сегменты для OPS',
            isDirectory: true,
            children: [
              {
                id: 1000249,
                title: 'Сегменты для внешней рекламы',
                isDirectory: true,
                children: [
                  {
                    id: 1000831,
                    title: 'Автодилеры',
                    isDirectory: false,
                  },
                  {
                    id: 1000772,
                    title: 'Cian',
                    isDirectory: false,
                  }
                ] 
              }
            ]
          }
        ]
      },
      {
        id: 3811,
        title: 'Сегменты Facetz',
        isDirectory: true,
        children: [
          {
            id: 3840,
            title: 'Образ жизни',
            isDirectory: true,
            children: [
              {
                id: 2681,
                title: 'Обзоры',
                isDirectory: false
              }
            ]
          }
        ]
      }
    ]
  }
]

Моё решение:

const traverseItems = (acc, currentNode, index, allNodes) => {
  const path = currentNode.name.split('/');
  const title = path[path.length - 1].replace(/("|')/g, '');
  const id = currentNode.id;

  const currentChildren = allNodes
    .filter(n => n.id !== id)
    .filter(n => n.name.includes(title));

  const isDirectory = currentChildren.length > 0 || id === 0;

  if (isDirectory) {
    return acc.concat([{
      id,
      title,
      isDirectory,
      children: currentChildren.reduce(traverseItems, acc)
    }]);
  } else {
    return acc.concat([{ id, title, isDirectory }]);
  }
};

const result = nodes.reduce(traverseItems, []);

Comments

[Roman]

1) Хабр
Классические алгоритмы и структуры данных на JavaScript

2)

Learning JavaScript Data Structures and Algorithms

Loiane Groner

Chapter 8
In this chapter, we will cover:
Tree terminology
Creating a tree data structure
Traversing a tree
Adding and removing nodes
The AVL tree


книга гуглится

исходники https://github.com/loiane/javascript-datastructure...

Answer 1

[0xD34F]

function getTree(data) {
  let root = data.find(n => n.id === 0);
  root = { title: root.name.slice(1,-1), id: root.id };

  data.filter(n => n.id !== 0).forEach(item => {
    const node = item.name.slice(1, -1).split('/').reduce((parent, title) => {
      if (!parent.children) {
        Object.assign(parent, { children: [], isDirectory: true });
      }
      let child = parent.children.find(m => m.title === title);
      if (!child) {
        child = { title };
        parent.children.push(child);
      }
      return child;
    }, root);
    Object.assign(node, { id: item.id, isDirectory: !!node.isDirectory });
  });

  return root;
}

Comments

[Дмитрий Есин]

Спасибо, эта рализация работает корректно для любых объёмов данных, хоть мне и не очень нравится такой подход =)

А можно поинтересоваться как составили алгортм? Взяли что-то конкретное или просто опыт и дело техники?

[0xD34F]

Дмитрий Есин, наверное опыт - собственно "составлять" ничего и не пришлось, как увидел эти имена, которые задают положение в результирующей структуре данных, сразу стало ясно, что можно просто перебирать их по частям и создавать отсутствующие элементы. Похожие задачи встречались (в том числе и тут, на Тостере).