Esta pregunta se basa en muchas similares, como ¿Construir un árbol de jerarquía a partir de una lista plana con un campo principal?
Sin embargo, el giro es que no hay identificación de los padres. p.ej
[ {id: 1, depth: 1, ...}, {id: 2, depth: 2, ...}, {id: 3, depth: 3, ...}, {id: 4, depth: 2, ...}, {id: 5, depth: 1, ...}, {id: 6, depth: 2, ...}, {id: 7, depth: 2, ...}, {id: 8, depth: 1, ...}, {id: 9, depth: 2, ...}, {id: 10, depth: 3, ...}, {id: 11, depth: 3, ...}, ] ¿Cuál es una forma eficaz de construir el siguiente árbol? Tenga en cuenta que los hijos siempre vienen después del padre, es decir, se puede ver el árbol desde el valor de depth . Por ejemplo, id 2 es un hijo de id 1 ya que su profundidad es 2 e id 1 tiene una profundidad de 1. id 3 es un hijo de id 2 ya que id 3 tiene una profundidad de 3. id 4 es un hijo de id 1 no id 3 porque id 4 tiene una profundidad de 2 (un paso hacia arriba) desde la profundidad de 3 de id 3 3
\\tree digram 1 2 3 4 5 6 7 8 9 10 11Debe tener valores como
[ {id:1, depth:1, children: [ {id: 2, depth: 2, children: [...]}, ... ]}, {id:5, depth:1, children: [...]}, {id:6, depth:1, children: [...]}, ]Puede usar una matriz para esto que tenga un índice para cada profundidad. En cada momento representará un camino desde la raíz (virtual) hasta el nodo actual. Cuando se trata de un nodo, su padre se ubicará en depth-1 , donde se puede insertar en la propiedad children de ese padre, y el nodo en sí se colocará en depth de índice:
function createForest(flatdata) { const path = [{ children: [] }]; for (const obj of flatdata) { path[obj.depth - 1].children.push(path[obj.depth] = { ...obj, children: [] }); } return path[0].children; } // demo const flatdata = [{id: 1, depth: 1},{id: 2, depth: 2},{id: 3, depth: 3},{id: 4, depth: 2},{id: 5, depth: 1},{id: 6, depth: 2},{id: 7, depth: 2},{id: 8, depth: 1},{id: 9, depth: 2},{id: 10, depth: 3},{id: 11, depth: 3}]; const roots = createForest(flatdata); console.log(roots); Si los valores de depth no corresponden a la profundidad real de los nodos, pero dejan huecos, utilice un "diccionario" (un objeto simple) para registrar el mapeo de los valores de propiedad de depth con la profundidad real con la que se corresponden:
function createForest(flatdata) { const path = [{ children: [] }]; const depthMap = { 0: 0 }; for (const obj of flatdata) { path[(depthMap[obj.depth] ??= path.length) - 1].children.push( path[depthMap[obj.depth]] = { ...obj, children: []} ); } return path[0].children; } // demo const flatdata = [{id: 1, depth: 10},{id: 2, depth: 20},{id: 3, depth: 30},{id: 4, depth: 20},{id: 5, depth: 10},{id: 6, depth: 20},{id: 7, depth: 20},{id: 8, depth: 10},{id: 9, depth: 20},{id: 10, depth: 30},{id: 11, depth: 30}]; const roots = createForest(flatdata); console.log(roots);Sin embargo, si la única irregularidad es que la profundidad no siempre comienza en 1, sino a veces en 2, será más eficiente prefijar los datos de entrada con un nodo ficticio de profundidad uno, use la primera función y luego elimine el nodo ficticio. "raíz" (con profundidad 1) del resultado.
Revise la matriz y agregue cada elemento al árbol, así como a un rastro de migas de pan. Cada elemento siguiente va como un elemento secundario al último o retrocede a través del rastro de migas de pan hasta la profundidad correcta donde debe insertarse:
const peek = arr => arr[arr.length-1]; function toTree(arr) { const tree = []; const trail = []; for (const item of arr) { while ((peek(trail)?.depth ?? 0) >= item.depth) { trail.pop(); } const current = peek(trail)?.children ?? tree; const treeNode = {...item, children: []}; current.push(treeNode); trail.push(treeNode); } return tree; } const array = [ {id: 1, depth: 1, }, {id: 2, depth: 2, }, {id: 3, depth: 3, }, {id: 4, depth: 2, }, {id: 5, depth: 1, }, {id: 6, depth: 2, }, {id: 7, depth: 2, }, {id: 8, depth: 1, }, {id: 9, depth: 2, }, {id: 10, depth: 3 }, {id: 11, depth: 3 }, ] console.log(toTree(array)); Esta solución clona cada elemento para agregar la propiedad .children . Si no es necesaria la clonación, item se puede mutar directamente.
Podría tomar una matriz de los últimos objetos insertados.
const data = [{ id: 1, depth: 1 }, { id: 2, depth: 2 }, { id: 3, depth: 3 }, { id: 4, depth: 2 }, { id: 5, depth: 1 }, { id: 6, depth: 2 }, { id: 7, depth: 2 }, { id: 8, depth: 1 }, { id: 9, depth: 2 }, { id: 10, depth: 3 }, { id: 11, depth: 3 }], result = data.reduce((r, { depth, ...o }) => { r[depth - 1].push({ ...o, children: r[depth] = [] }); return r; }, [[]])[0]; console.log(result); .as-console-wrapper { max-height: 100% !important; top: 0; }