Как можно быстро перестроить дерево?

Question

[Artem0071]

Как можно быстро переделать из такой структуры данных:

[
  id: 1,
  parent_id: null,
  ...
],
[
  id: 2,
  parent_id: 1
],
[
  id: 3,
  parent_id: 2
],
...

В такую:

[
  id: 1,
  children: [
    [
      id: 2,
      children: [
        [
          id: 3,
          children: []
        ]
      ]
    ]
  ]
]

Answer 1

[ThunderCat]

рекурсия... классика...
на жс я не настолько крут, и лениво переписывать. Есть классические статьи, как тут или тут, если хватит желания разобраться - смотрите и адаптируйте. Ничего космического там нет. Проход по элементам, каждый раз выбирая очередной встречающийся парент и если внутри него встречается принадлежащий этому паренту элемент - для него опять делается выборка элементов этой же функцией. Подход универсален для любого количества элементов и любого уровня вложенности.

Comments

[Сергей delphinpro]

Сначала лайкнул, потом подумал — а зачем здесь рекурсия? Можно же за один проход составить дерево

[longclaps]

Сергей delphinpro, ты не поверишь - рекурсию тоже иногда можно провести в один проход.

[ThunderCat]

Сергей delphinpro, а кстати да, если больше ветвей не предусмотрено...

[ThunderCat]

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

[Artem0071]

Все повыпендривались?)
Я только нашел самых верхних предков и их первых потомков, но как дальше надо?

refactorCategories (categories) {
      let parents = this.findFirstParents(categories)

      parents.forEach(parent => {
        parent.children = this.findChildren(categories, parent.id)
      })
    },
    findChildren (array, id) {
      return array.filter(item => {
        return item.parent_id === id
      })
    },
    findFirstParents (categories) {
      return categories.filter(category => {
        return !category.parent_id
      })
    }

[longclaps]

ThunderCat, ты не поверишь - бывают такие языки, что или рекурсия - или никак )
А к вопросу - входные данные бывают разными. Например:

[
  id: 1,
  parent_id: null,
],
[
  id: 2,
  parent_id: null,
],
[
  id: 3,
  parent_id: null,
]

Как из этого собрать (в один проход) дерево, когда оно - не дерево?

[longclaps]

Artem0071, пока что по-настоящему выпендрился только ты со странным кодом с асимптотикой O(N^2).

[ThunderCat]

longclaps, хм, то что нет ветвей не значит что не дерево, просто все ветви будут нулевыми, то есть оно уже дерево. Вернется как есть. Дерево это не массив данный в текущий момент, это структура с ВОЗМОЖНОЙ вложенностью.

[Artem0071]

longclaps, я тут пытался еще помучиться с рекурсией, но пишет "Maximum call stack size exceeded"

refactorCategories (categories) {
      console.log(this.getChildren(categories))
    },
    getChildren (categories, parentId = null) {
      categories.forEach(category => {
        if (category.parent_id === parentId) {
          category.children = this.getChildren(categories, category.parent_id)
        }
      })
      return categories
    }

[longclaps]

ThunderCat, вики.

[ThunderCat]

longclaps, спасибо, я еще помню ТГ по институту. Только к чему вы это? parent_id: null в структуре есть, значит предполагается вложенность структуры.

[Artem0071]

longclaps, что то заработало, но в children пишет undefined

refactorCategories (categories) {
      let parents = this.findFirstParents(categories)

      parents.forEach(parent => {
        parent.children = this.getChildren(categories, parent.id)
      })

      console.log(parents)
    },
    getChildren (categories, parentId) {
      return categories.filter(category => {
        return category.parent_id === parentId
      }).map(category => {
        category.children = this.getChildren(categories, category.id)
      })

PS.. ой, забыл в map добавить return

[longclaps]

Artem0071,

data = [
    {id: 1, parent_id: null},
    {id: 2, parent_id: 1},
    {id: 3, parent_id: 2}];

tree = new Map();
for (node of data) {
    if (tree[node.parent_id] === undefined) {
        tree[node.parent_id] = [node.id]
    } else {
        tree[node.parent_id].push(node.id)
    }
}
console.log(tree);

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