Построение древовидной структуры из плоского массива
У меня есть массив объектов. Каждый из них содержит свойство «lv», которое является целым числом >= 0.
[
{lv: 0, name: "A"},
{lv: 1, name: "B"},
{lv: 1, name: "C"},
{lv: 2, name: "D"},
{lv: 3, name: "E"},
{lv: 1, name: "F"},
{lv: 0, name: "G"},
]
Он экспортирован из старого программного обеспечения и представляет собой древовидную структуру: «lv» обозначает глубину узла, а его место в дереве всегда относительно предыдущего узла в массиве. Итак, первый объект (A) имеет уровень 0 (корневой); B — это уровень 1 и, следовательно, является дочерним элементом предыдущей записи уровня 0 (A); C также является уровнем 1 и, следовательно, является братом B (а также дочерним элементом A); и так далее. В результате структура выглядит следующим образом:
├ A
│ ├ B
│ ├ C
│ │ └ D
│ │ └ E
│ └ F
└ G
Я хочу написать функцию для преобразования этого плоского массива в структуру, которая бы более точно отражала древовидную структуру, например:
[
{
name: "A",
children: [
{
name: "B",
children: null
},
{
name: "C",
children: [
{
name: "D",
children: [
{
name: "E",
children: null
}
]
}
]
},
{
name: "F",
children: null
}
]
},
{
name: "G",
children: null
}
]
Таким образом, в основном каждый узел имеет дочерние элементы, перечисленные в массиве под свойством «дети», рекурсивно.
Я написал следующую рекурсивную функцию, но она прерывается, когда встречает узел, который возвращается вверх по дереву (например, узел уровня 1, следующий за узлом уровня 3):
function buildTree(arr) {
let siblings = [], children = null
while (arr.length) {
let node = arr.shift()
if (arr.length) {
let nodeLv = +node.lv
let nextNodeLv = +arr[0].lv
if (nextNodeLv > nodeLv) {
children = buildTree(arr)
}
}
let newNode = {
name: node.name,
children: children
}
siblings.push(newNode)
}
return siblings
}
Это дает мне следующую структуру вместо той, что изображена выше:
└ A
├ B
└ C
└ D
└ E
└ F
└ G
Так что в принципе он отлично работает при более глубоком построении, но не может пойти другим путем (от E к F или от F к G).
Что я здесь делаю не так? Есть ли лучший способ подойти к этому?
имеет смысл; ты справляешься if (nextNodeLv > nodeLv), но нет if (nextNodeLv < nodeLv)
(nextNodeLv > nodeLv) — это случай, когда у текущего узла есть дочерние элементы, поэтому нам придется пойти глубже, выполнив функцию рекурсивно; остальные случаи обрабатываются неявно, т. е. мы просто позволяем функции работать, создаем узел и возвращаем массив. Я не говорю, что я прав (очевидно, поскольку на самом деле это не работает), но это был мой мыслительный процесс.
![Безумие обратных вызовов в javascript [JS]](https://i.imgur.com/WsjO6zJb.png)
Ответы 3
Используйте стек, где его текущее состояние представляет собой путь к текущему уровню с экземплярами узлов. Добавьте текущий узел в родительский список children, который находится наверху стека. Вытаскивайте узлы из этого стека, когда уровень снижается.
function makeHierarchy(flat) {
const hierarchy = [];
const stack = [{children: hierarchy}];
for (const {lv, name} of flat) {
while (lv < stack.length - 1) stack.pop();
const obj = {name, children: []};
stack.at(-1).children.push(obj);
stack.push(obj);
}
return hierarchy;
}
// Demo with data from question
const flat = [{lv: 0, name: "A"},{lv: 1, name: "B"},{lv: 1, name: "C"},{lv: 2, name: "D"},{lv: 3, name: "E"},{lv: 1, name: "F"},{lv: 0, name: "G"},];
const hierarchy = makeHierarchy(flat);
console.info(hierarchy);Обратите внимание, что здесь для конечных узлов свойство children установлено в пустой массив. В данном случае это кажется более последовательным, чем использование null. Если вам действительно нужны значения null, используйте этот вариант:
function makeHierarchy(flat) {
const hierarchy = [];
const stack = [{children: hierarchy}];
for (const {lv, name} of flat) {
while (lv < stack.length - 1) stack.pop();
const obj = {name, children: null};
(stack.at(-1).children ??= []).push(obj);
stack.push(obj);
}
return hierarchy;
}
const flat = [{lv: 0, name: "A"},{lv: 1, name: "B"},{lv: 1, name: "C"},{lv: 2, name: "D"},{lv: 3, name: "E"},{lv: 1, name: "F"},{lv: 0, name: "G"},];
const hierarchy = makeHierarchy(flat);
console.info(hierarchy);Это можно сделать без рекурсии. Сначала вы можете определить правильного родителя для каждого элемента, а затем переместить каждый элемент на правильное место в иерархии.
const data = [{"lv":0,"name":"A"},{"lv":1,"name":"B"},{"lv":1,"name":"C"},{"lv":2,"name":"D"},{"lv":3,"name":"E"},{"lv":1,"name":"F"},{"lv":0,"name":"G"}]
// assign a parent to each item
data.forEach((e, i, r) => {
let last = r[i-1];
if (last) {
e.parent = last;
for(let j=(last.lv - e.lv)+1; j--;) e.parent = e.parent.parent;
}
})
// the result will directly contain the items with no parent
let result = data.filter(e => !e.parent);
// add each item to a children array created for its parent
data.filter(e => e.parent).forEach(e => (e.parent.children ??= []).push(e))
// delete unnecessary propertoes
data.forEach(e => {
delete e.parent
delete e.lv
if (!e.children?.length) e.children = null
})
console.info(result)Вам не нужен стек или рекурсия, просто запомните последние элементы уровней, чтобы поместить к ним дочерних элементов:
const arr = [
{lv: 0, name: "A"},
{lv: 1, name: "B"},
{lv: 1, name: "C"},
{lv: 2, name: "D"},
{lv: 3, name: "E"},
{lv: 1, name: "F"},
{lv: 0, name: "G"},
]
const result = [], last = [{children: result}]; // collect last nodes of levels
for(const {lv, name} of arr){
const node = {name, children: null};
(last[lv].children ??= []).push(node);
last[lv + 1] = node;
}
console.info(result);.as-console-wrapper{max-height:100%!important};И бенчмаркинг:
` Chrome/125
--------------------------------------------------------------------------------------
> n=7 | n=70 | n=700 | n=7000
Alexander ■ 1.00x x1m 111 | ■ 1.00x x100k 84 | ■ 1.00x x100k 858 | ■ 1.00x x10k 942
trincot 1.14x x1m 127 | 1.11x x100k 93 | 1.13x x10k 97 | 1.16x x1k 109
Andrew 6.20x x1m 688 | 5.82x x100k 489 | 5.26x x10k 451 | 5.98x x1k 563
-------------------------------------------------------------------------------------- `
Открыта детская площадка
const $chunk = [
{lv: 0, name: "A"},
{lv: 1, name: "B"},
{lv: 1, name: "C"},
{lv: 2, name: "D"},
{lv: 3, name: "E"},
{lv: 1, name: "F"},
{lv: 0, name: "G"},
]
const $input = [], arr = $input, data = $input;
// @benchmark Alexander
const result = [], last = [{children: result}]; // collect last nodes of levels
for(const {lv, name} of arr){
const node = {name, children: null};
(last[lv].children ??= []).push(node);
last[lv + 1] = node;
}
result;
// @benchmark trincot
function makeHierarchy(flat) {
const hierarchy = [];
const stack = [{children: hierarchy}];
for (const {lv, name} of flat) {
while (lv < stack.length - 1) stack.pop();
const obj = {name, children: null};
(stack.at(-1).children ??= []).push(obj);
stack.push(obj);
}
return hierarchy;
}
makeHierarchy(arr);
// @benchmark Andrew
{
// assign a parent to each item
data.forEach((e, i, r) => {
let last = r[i-1];
if (last) {
e.parent = last;
for(let j=(last.lv - e.lv)+1; j--;) e.parent = e.parent.parent;
}
})
// the result will directly contain the items with no parent
let result = data.filter(e => !e.parent);
// add each item to a children array created for its parent
data.filter(e => e.parent).forEach(e => (e.parent.children ??= []).push(e))
// delete unnecessary propertoes
data.forEach(e => {
delete e.parent
delete e.lv
if (!e.children?.length) e.children = null
})
result;
}
/*@skip*/ fetch('https://cdn.jsdelivr.net/gh/silentmantra/benchmark/loader.js').then(r => r.text().then(eval));Круто, если бы я об этом подумал :)
очень приятно, Алекс
«Тебе не нужна стопка»: но last — это твоя стопка.
@trincot стек, который вы помещаете и извлекаете в/из. есть только карта и последние предметы на уровне, никаких операций push/pop, может быть, я не понимаю, пожалуйста, укажите мне цитату из Википедии, может быть
@trincot изначально это был объект, но я проверил, что массив работает быстрее с индексами действительных чисел (что lv так и есть)
Поможет ли сортировка списка узлов?