Explorando Tree Traversal en JavaScript: Inorder, Preorder y Postorder con ejemplos

Tree Traversal es un concepto fundamental en informática que implica visitar sistemáticamente cada nodo en una estructura de datos de árbol. A través del recorrido del árbol, podemos procesar los nodos en un orden predeterminado, lo que facilita operaciones como buscar, clasificar y evaluar expresiones.

En este artículo, exploraremos tres de los métodos de recorrido de árboles más utilizados: en orden, en orden previo y en orden posterior.

A través de ejemplos claros y concisos implementados en JavaScript, obtendrá una sólida comprensión de estas técnicas transversales.

Definición de estructura de árbol

Antes de profundizar en los algoritmos de recorrido del árbol, definamos la estructura que usaremos para el árbol binario. El árbol constará de nodos, donde cada nodo contiene un valor y referencias a sus nodos secundarios izquierdo y derecho.

 function TreeNode(val = 0, left = null, right = null) { this.val = val; this.left = left; this.right = right; }

Ahora que hemos definido la estructura del árbol, podemos continuar con la exploración de los tres métodos de recorrido del árbol.

Recorrido en orden

El recorrido en orden sigue el siguiente patrón de nodos visitantes en un árbol binario: el algoritmo primero atraviesa el subárbol izquierdo, luego visita el nodo actual y finalmente atraviesa el subárbol derecho. Esto asegura que los nodos se visiten en orden ascendente si el árbol representa una estructura de datos ordenados.

 A / \ BC / \ / \ DEFG // Inorder traversal result: D -> B -> E -> A -> F -> C -> G

Recorrido en Orden Recursivo

1. Compruebe si el nodo actual es nulo. Si es así, regresa.

   
   

2. Llame recursivamente a la función en el subárbol izquierdo.

   
   

3. Visite el nodo actual.

   
   

4. Llame recursivamente a la función en el subárbol derecho.

 function inorderRecursive(tree) { const result = []; function inorderTraverse(node) { if (!node) return; inorderTraverse(node.left); result.push(node.val); inorderTraverse(node.right); } inorderTraverse(tree); return result; }

Recorrido en orden no recursivo

1. Inicialice una pila vacía y establezca el nodo actual en la raíz del árbol.

   
   

2. Iterar mientras la pila no está vacía o el nodo actual no es nulo.

   • Empuje todos los nodos izquierdos en la pila hasta llegar a un hijo izquierdo nulo.

   • Extraiga un nodo de la pila, visítelo y establezca el nodo actual en su hijo derecho.

     
     

3. Repita el paso 2 hasta que la pila esté vacía y el nodo actual sea nulo.

 function inorderRecursive(tree) { const stack = []; const result = []; let currentNode = tree; while (currentNode || stack.length) { while (currentNode) { stack.push(currentNode); currentNode = currentNode.left; } const node = stack.pop(); result.push(node.val); currentNode = node.right; } return result; }

Recorrido de pedido anticipado

En el recorrido de preorden, el algoritmo primero visita el nodo actual, luego atraviesa el subárbol izquierdo y finalmente atraviesa el subárbol derecho. Este orden asegura que los nodos se visiten de manera "de arriba hacia abajo", comenzando desde la raíz y moviéndose hacia las hojas.

 A / \ BC / \ / \ DEFG // Preorder traversal result: A -> B -> D -> E -> C -> F -> G

Recorrido de orden anticipado recursivo

1. Compruebe si el nodo actual es nulo. Si es así, regresa.

   
   

2. Visite el nodo actual.

   
   

3. Llame recursivamente a la función en el subárbol izquierdo.

   
   

4. Llame recursivamente a la función en el subárbol derecho.

   
   

 function preorderRecursive(tree) { const result = []; function preorderTraverse(node) { if (!node) return; result.push(node.val); preorderTraverse(node.left); preorderTraverse(node.right); } preorderTraverse(tree); return result; }

Recorrido de orden anticipado no recursivo

1. Comience con una pila vacía e inserte el nodo raíz en la pila.

   
   

2. Inicialice una matriz vacía para almacenar el resultado del recorrido de preorden.

   
   

3. Ingrese un ciclo while que se ejecuta hasta que la pila esté vacía.

   
   

4. Extraiga un nodo de la pila y visítelo agregando su valor a la matriz de resultados.

   
   

5. Si el nodo tiene un hijo derecho, empuje el hijo derecho a la pila.

   
   

6. Si el nodo tiene un hijo izquierdo, empuje el hijo izquierdo a la pila.

   
   

7. Repita los pasos 3 a 6 hasta que la pila esté vacía.

 function preorderTraversal(root) { if (!root) return []; const stack = [root]; const result = []; while (stack.length) { const node = stack.pop(); result.push(node.val); if (node.right) stack.push(node.right); if (node.left) stack.push(node.left); } return result; }

Recorrido posterior al pedido

En este recorrido, el algoritmo primero atraviesa el subárbol izquierdo, luego el subárbol derecho y finalmente visita el nodo actual. Este orden asegura que los nodos sean visitados de manera "de abajo hacia arriba", comenzando desde las hojas y moviéndose hacia la raíz.

 A / \ BC / \ / \ DEFG // Postorder traversal result: D -> E -> B -> F -> G -> C -> A

Recorrido Postorden Recursivo

1. Compruebe si el nodo actual es nulo. Si es así, regresa.

   
   

2. Llame recursivamente a la función en el subárbol izquierdo.

   
   

3. Llame recursivamente a la función en el subárbol derecho.

   
   

4. Visite el nodo actual.

 function postorderRecursive(tree) { const result = []; function postorderTraverse(node) { if (!node) return; postorderTraverse(node.left); postorderTraverse(node.right); result.push(node.val); } postorderTraverse(tree); return result; }

Recorrido posorden no recursivo

1. Comience con una pila vacía e inserte el nodo raíz en la pila.

   
   

2. Inicialice una matriz vacía para almacenar el resultado del recorrido posterior al pedido.

   
   

3. Ingrese un ciclo while que se ejecuta hasta que la pila esté vacía.

   
   

4. Obtenga el nodo superior de la pila (sin eliminarlo).

   
   

5. Si el nodo tiene un hijo izquierdo, coloque el hijo izquierdo en la pila y establezca el hijo izquierdo del nodo actual en nulo.

   
   

6. Si el nodo tiene un hijo derecho, inserte el hijo derecho en la pila y establezca el hijo derecho del nodo actual en nulo.

   
   

7. Si el nodo no tiene un hijo izquierdo ni derecho, es un nodo hoja. Extraiga el nodo de la pila y agregue su valor a la matriz de resultados.

   
   

8. Repita los pasos 4 a 7 hasta que la pila esté vacía.

 function postorderTraversal(root) { if (!root) return []; const stack = [root]; const result = []; while (stack.length) { const node = stack[stack.length - 1]; if (node.left) { stack.push(node.left); node.left = null; } else if (node.right) { stack.push(node.right); node.right = null; } else { result.push(stack.pop().val); } } return result; }

Conclusión

Espero que ahora tenga una comprensión clara de las diferencias entre el recorrido inorder, preorder y postorder en JavaScript. Con el conocimiento y los ejemplos proporcionados, ahora está equipado para aplicar estas técnicas a sus propias tareas y proyectos de manera efectiva.