Вы можете сохранить ссылку на каждый узел по ID в объекте и построить дерево, пока вы go. Поскольку мы можем встретить ссылки на записи, которые еще не видели, мы тем временем создадим заглушки (состоящие только из дочернего массива) и добавим остальные их поля позже.
Таким образом, мы есть только один l oop.
Кажется, у вас есть своего рода вертикальный двойной список, сохраняющий как родительский идентификатор в дочерних элементах, так и идентификаторы дочерних в родительском, но нам нужен только один из те, чтобы построить дерево. Мы будем использовать родительский идентификатор, хранящийся у каждого ребенка. (Обратите внимание, что это предполагает, что ваша структура непротиворечива без несбалансированных отношений или висячих ссылок.)
Для простоты мы создадим один root узел, чьи дочерние элементы мы вернем в конце, так что мы не будем приходится обрабатывать узлы без родителя по-другому.
Тогда вы можете написать код, подобный этому:
function makeTree (rows) {
// Use a symbol to denote the root ID to avoid clashes with any real IDs
const ROOT = Symbol('ROOT')
// Node index, by ID
// Add a root node from the start
const nodes = { [ROOT]: { children: [] } }
// Helper function to return an existing node or create a stub if not existing
const getNodeOrCreateStub = id => nodes[id] || (nodes[id] = { children: [] })
for (const row of rows) {
// Add current row to index, merging data with existing stub, if any.
// This keeps any existing references in other nodes' children arrays intact
// because Object.assign mutates the first object passed to it and returns the
// same object.
const node = Object.assign(getNodeOrCreateStub(row.id), row)
// Remove unwanted properties.
delete node.parentId
delete node.childrenIds
// Get parent or create parent stub if parent node not already existing
const parent = getNodeOrCreateStub(row.parentId || ROOT)
// Add current node as child to parent
parent.children.push(node)
}
// Return children of root node
return nodes[ROOT].children
}
Обратите внимание, что этот код в настоящее время также создает пустые массивы children в конечных узлах, в отличие от вашего примера выше. Однако я думаю, что это делает код проще, потому что он не должен обрабатывать листовые узлы иначе, ни при создании дерева, ни при его чтении позже! (Вам не нужно было бы делать children && children.length, чтобы проверить детей, вы всегда можете просто обратиться к children напрямую.)
Чтобы изменить это и получить результат в точности, как в вашем примере, вы изменили бы код следующий:
// Change this...
const getNodeOrCreateStub = id => nodes[id] || (nodes[id] = { children: [] })
// ...to this:
const getNodeOrCreateStub = id => nodes[id] || (nodes[id] = {})
// Also change this...
parent.children.push(node)
// ...to this:
if (!parent.children) parent.children = []
parent.children.push(node)
// ...or to this:
parent.children = [...parent.children || [], node]