in

Estructura de datos y algoritmos: cruce de árboles

inorder traversal

El recorrido es un proceso para visitar todos los nodos de un árbol y también puede imprimir sus valores. Debido a que 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
  • Preordenar Traversal
  • 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.

Traversal 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 en orden, la salida producirá valores clave ordenados en orden ascendente.

En orden transversal

Partimos de A, y siguiendo el recorrido en orden, nos movemos a su subárbol izquierdo B. B tambié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.

Preordenar Traversal

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

Preorden transversal

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. B también se atraviesa el pedido anticipado. El proceso continúa hasta que se visitan todos los nodos. La salida del recorrido del pedido por adelantado 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.

Traslado posterior a la orden

Partimos de A, y siguiendo el recorrido posterior al pedido, primero visitamos el subárbol izquierdo B. B tambié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í.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

java deadlock

Interbloqueo en Java – javatpoint

apple touch icon@2

¿Cuál es la diferencia entre salida (0) y salida (1) en C?