Estructura de datos y algoritmos: cruce de árboles

El recorrido es un proceso para visitar todos los nodos de un árbol y también puede imprimir sus valores. Porque todos los nodos están conectados a través de bordes (enlaces), siempre comenzamos desde el nodo raíz (cabeza). Es decir, no podemos acceder aleatoriamente a un nodo en un árbol. Hay tres formas que usamos para atravesar un árbol:

• Recorrido en orden
• Traversal de reserva
• Recorrido posterior al pedido

Generalmente, recorremos un árbol para buscar o ubicar un elemento o clave en el árbol o para imprimir todos los valores que contiene.

Recorrido en orden

En este método de recorrido, primero se visita el subárbol izquierdo, luego la raíz y luego el subárbol derecho. Siempre debemos recordar que cada nodo puede representar un subárbol en sí mismo.

Si se atraviesa un árbol binario in-order, la salida producirá valores clave ordenados en orden ascendente.

Partimos de A, y siguiendo el recorrido en orden, nos movemos a su subárbol izquierdo B. Btambién se recorre en orden. El proceso continúa hasta que se visitan todos los nodos. La salida del recorrido en orden de este árbol será:

D → B → E → A → F → C → G

Algoritmo

Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree.

Traversal de reserva

En este método de recorrido, primero se visita el nodo raíz, luego el subárbol izquierdo y finalmente el subárbol derecho.

Partimos de Ay, después de realizar el pedido por adelantado, primero visitamos A sí mismo y luego moverse a su subárbol izquierdo B. Btambién se atraviesa el pedido anticipado. El proceso continúa hasta que se visitan todos los nodos. La salida del recorrido de la reserva de este árbol será:

A → B → D → E → C → F → G

Algoritmo

Until all nodes are traversed −
Step 1 − Visit root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse right subtree.

Recorrido posterior al pedido

En este método de recorrido, el nodo raíz se visita en último lugar, de ahí el nombre. Primero atravesamos el subárbol izquierdo, luego el subárbol derecho y finalmente el nodo raíz.

Partimos de A, y siguiendo el recorrido posterior al pedido, primero visitamos el subárbol izquierdo B. Btambién se atraviesa después del pedido. El proceso continúa hasta que se visitan todos los nodos. La salida del recorrido posterior al pedido de este árbol será:

D → E → B → F → G → C → A

Algoritmo

Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.

Para comprobar la implementación en C de la travesía de árboles, haga clic aquí .