Actualmente estoy atascado con un problema que cuando comencé no parecía demasiado difícil de resolver para mí, pero ahora estoy atascado durante un par de horas, así que aquí vamos:
Dado este árbol/objetos anidados:
const tree = { value: 50, children: [ { value: 17, children: [ { value: 12, children: [ { value: 9, children: null }, { value: 14, children: null } ] }, { value: 23, children: null } ] }, { value: 72, children: [ { value: 54, children: [ { value: 67, children: null } ] }, { value: 76, children: null } ] } ], }Estoy tratando de encontrar una función que me dé la ruta a un valor
function findPath(tree, target){ ... }y la función devolverá algo como
findPath(tree, 67); <==============> [50, 72, 54, 67]Soy nuevo en el código. Espero que te ayuden a solucionar esto. Gracias.
Una opción con árboles es la recursividad. Busque recursivamente a los niños hasta que se encuentre el valor. En el camino de regreso, construya la matriz. No estoy seguro de que este sea el más eficiente, pero funciona.
const tree = { value: 50, children: [{ value: 17, children: [{ value: 12, children: [{ value: 9, children: null }, { value: 14, children: null } ] }, { value: 23, children: null } ] }, { value: 72, children: [{ value: 54, children: [{ value: 67, children: null }] }, { value: 76, children: null } ] }], }; function findPath(tree, target) { // The value of this node let currentValue = tree.value; if (currentValue == target) return [target]; for (let t of Object.entries(tree)) { // Search children if (t[0] == "children" && t[1]) { for (let child of t[1]) { let found = findPath(child, target); if (found) { return [currentValue].concat(found); } } } } // Not found in this branch return null; } console.log(findPath(tree, 67));Puede usar la recursividad para encontrar la ruta (vea los comentarios en el código):
function findPath({ value, children }, target) { if(value === target) return [value] // if the value is found return it wrap in an array for(const child of children ?? []) { // iterate the children or an empty array const leaf = findPath(child, target) // use findPath on all children if(leaf) return [value, ...leaf] // if a leaf is found (not null) spread it to the current array, and return it } return null } const tree = {"value":50,"children":[{"value":17,"children":[{"value":12,"children":[{"value":9,"children":null},{"value":14,"children":null}]},{"value":23,"children":null}]},{"value":72,"children":[{"value":54,"children":[{"value":67,"children":null}]},{"value":76,"children":null}]}]} const result = findPath(tree, 67) console.log(result)Aquí hay una solución que usa la búsqueda primero en profundidad , un algoritmo transversal de árbol.
function findPath(tree, target) { const path = []; const stack = [tree]; while (stack.length) { let curr = stack.pop(); path.push(curr.value); if (curr.value === target) return path; if (curr.children !== null) { curr.children.forEach(child => stack.push(child)); } else { path.pop(); } } // target not found return []; } const tree = {"value":50,"children":[{"value":17,"children":[{"value":12,"children":[{"value":9,"children":null},{"value":14,"children":null}]},{"value":23,"children":null}]},{"value":72,"children":[{"value":54,"children":[{"value":67,"children":null}]},{"value":76,"children":null}]}]}; console.log(findPath(tree, 67));