Quiero pedir ayuda en una tarea donde tengo que atravesar un arbol y obtener como resultado:
[ 4, 2, 5, 7, 6, 3, 1 ]La clase:
class Traversal { postOrderTraversal(tree) { // ...code here } }mi objeto:
const tree = { value: 1, children: [ { value: 2, children: [ { value: 4, children: [] } ], }, { value: 3, children: [ { value: 5, children: [], }, { value: 6, children: [ { value: 7, children: [], }, ], }, ], }, ], };Ilustración de ejemplo (tenemos un máximo de dos hijos en cada nodo):
+----------------+ | value: 1 | +----------------+ / \ / \ +----------------+ +----------------+ | value: 2 | | value: 3 | +----------------+ +----------------+ / / \ / / \ +----------------+ +----------------+ +----------------+ | value: 4 | | value: 5 | | value: 6 | +----------------+ +----------------+ +----------------+ / / +----------------+ | value: 7 | +----------------+Si alguien puede ayudar con esto, use javascript simple para que pueda entenderlo mejor.
Esta es probablemente la implementación más fácil que se me ocurre. Dadas solo dos líneas de código, hay muy poco espacio para la explicación:
function *postorder(t) { for (child of t.children) yield *postorder(child) yield t.value } const mytree = {value:1,children:[{value:2,children:[{value:4,children:[]}]},{value:3,children:[{value:5,children:[]},{value:6,children:[{value:7,children:[]}]}]}]} console.log(Array.from(postorder(mytree))) [4,2,5,7,6,3,1] Confundir el recorrido con las clases, aunque es posible, no le reporta ningún beneficio. postorder permanece sin cambios -
function *postorder(t) { for (child of t.children) yield *postorder(child) yield t.value } class Traversal { postorder(t) { return Array.from(postorder(t)) } } const mytree = {value:1,children:[{value:2,children:[{value:4,children:[]}]},{value:3,children:[{value:5,children:[]},{value:6,children:[{value:7,children:[]}]}]}]} const q = new Traversal() console.log(q.postorder(mytree)) Comparar con preorder . El único cambio necesario para lograr este recorrido es cambiar el orden de las dos líneas:
function *preorder(t) { yield t.value for (child of t.children) yield *preorder(child) } const mytree = {value:1,children:[{value:2,children:[{value:4,children:[]}]},{value:3,children:[{value:5,children:[]},{value:6,children:[{value:7,children:[]}]}]}]} console.log(Array.from(preorder(mytree))) [1,2,4,3,5,6,7]Como suele ser el caso con este tipo de algoritmos de visitas a árboles, su mejor apuesta es la recursividad: cada nodo en el árbol debe devolver su propio valor, después de los valores de sus hijos. Ciertamente, hay formas más cortas y eficientes de hacer esto que las que he escrito a continuación, pero he estructurado el código de tal manera que está claro cuándo termina la recursión (el nodo actual no tiene hijos) y en qué orden los valores se agregan a la matriz devuelta para facilitar la comprensión.
function postOrderTraversal(node) { if (node.children.length === 0) { return [node.value]; } else { var arr = []; for (var i = 0; i < node.children.length; i++) { var childValues = postOrderTraversal(node.children[i]); arr = arr.concat(childValues); } arr.push(node.value); return arr; } }Creo que usar la recursión es bueno para demostrar cómo funciona el orden posterior. Encontré que esta es una solución relativamente sencilla.
class Traversal { postOrderTraversal(tree, arr=[]) { if(tree) { this.postOrderTraversal(tree.children[0], arr); this.postOrderTraversal(tree.children[1], arr); arr.push(tree.value); } return arr; } } Dado que su conjunto de datos es el de un árbol, asumo que children[0] se considera el nodo izquierdo y children[1] se considera el nodo derecho.