Autor: Diego Peña Sadornil

Este artículo es una continuación del artículo “Árboles binarios. Un bosque de datos y cómo orientarnos” que, en caso de no estar familiarizado con los conceptos básicos, se recomienda leer antes de continuar con este artículo.

En el artículo anterior, explicábamos que es un árbol binario, una estructura de datos compuesta por nodos conectados entre sí por punteros. Cada nodo puede tener uno, dos o ningún hijo, a estos hijos se les apuntará con los punteros y será la manera de acceder a ellos. También vimos la utilidad de estas estructuras para acceder rápidamente a datos y cómo para hacerlo tenemos que conocer bajo qué normas está regido el árbol que queremos investigar. Más adelante vimos ejemplos de su uso, casos del día a día y concluimos viendo un pequeño fragmento de código que nos mostraba cómo se trabaja con estas estructuras en el ordenador.

Ahora que entendemos para qué usar estos árboles, es momento de ver cómo crearlos y, más importante si cabe, cómo recorrerlos para recoger o cultivar sus datos respetando la estructura con la que fueron creados. Al igual que en la vida real, distintos árboles tienen distintos métodos de cosecha. En informática, a estos métodos se les conoce como traversals (recorridos), y determinan en qué orden visitaremos los nodos de un árbol.                

En este artículo exploraremos los cuatro tipos principales de recorridos: Preorder, Postorder, Inorder y Level-order. Aprenderemos con ejemplos sus diferencias, cuándo conviene usar cada uno y veremos ejemplos prácticos de su aplicación. Como cierre, implementaremos estos métodos en código para visualizar cómo funcionan en la práctica.

2. Los 4 jinetes del crash:

En informática, cuando un código produce un error inesperado que provoca la finalización del programa se le conoce como crash. Corregir su origen puede ser un completo dolor de cabeza y podríamos ver esta interrupción espontánea como un apocalipsis, de ahí la comparación de los jinetes. Un programa que había estado funcionando correctamente llega a su fin dejando posibles secuelas por su cierre inoportuno, datos sin almacenar, archivos corruptos y más.

Este estado de crash es fácilmente alcanzable con los recorridos que veremos porque si se quedan abiertos de manera indefinida ya sea porque no los limitamos bien o porque entran en bucles podrían alcanzarse crashes por límite de memoria excedido o límite de tiempo alcanzado, que créeme son más comunes de lo que parecen. Cabe recalcar que los métodos aplicados para la búsqueda se pueden usar tanto para la lectura completa de un árbol como para la búsqueda de un elemento siguiendo un único camino. Pondremos como ejemplo la lectura completa del árbol, ya que de esta manera las diferencias serán más visuales.

Antes de ver a dichos jinetes, debemos entender un concepto clave: la recursión. La recursión es un término que se usa en la informática cuando una función se llama a sí misma. Para que no se llame indefinidamente, lo que hacemos es definir unos casos básicos antes de la llamada. En caso de que se cumpla alguno de estos casos básicos la llamada nunca llega a ocurrir y finaliza el bucle. Es importante que sean definidos correctamente ya que sino llegaremos al temido crash.

La manera en la que funcionan las llamadas a funciones recursivas es como si en una barra de pesas de gimnasio, fuésemos añadiendo pesas. Para sacar a las primeras que hemos metido hay que antes sacar a las últimas. Similarmente, para “cerrar” la primera llamada, tenemos que cerrar las posteriores. Esto además nos permitirá “volver” por los caminos, pues con cada llamada es como si se guardase un punto de control en el nodo desde el que se realiza dicha llamada.

2.1. Preorder traversal:

En este daremos prioridad al nodo, después al hijo izquierdo y por último al hijo derecho. Este método es útil en caso de árboles de expresiones, donde queremos ver el prefijo. Por ejemplo, se usan árboles de expresiones en las calculadoras para procesar operaciones matemáticas. Esto lo vimos en el artículo anterior.

Para programar el código al igual que en el artículo anterior usamos Python, gracias a su sintaxis sencilla, un nombrado lógico de variables y un poco de conocimiento de inglés podemos ver que el código es fácilmente entendible. Primero definimos una función a la que pasamos un nodo y una lista de valores. En caso de que el nodo tenga un valor no nulo y por tanto exista, añadiremos su valor a la lista de valores. Luego usaremos recursividad para repetir este proceso con su hijo izquierdo y luego con el derecho.

2.2. Inorder traversal:

Tal vez por el nombre, ya sepas que viene ahora. Si preorder priorizaba el nodo y luego hijos izquierdo y derecho en ese orden, inorder priorizará el hijo izquierdo, nodo y por último hijo de derecho. Este método se usa en BST o búsqueda en árbol binario, ya que cuando un árbol se administra con una regla, como la propuesta en el artículo anterior, en la que el hijo derecho tendrá un valor mayor que el nodo en el que nos encontramos y toda su descendencia izquierda. Si tomamos los caminos extremos, todo izquierda y todo derecha, obtendremos el mínimo y máximo valor del árbol y el resto de valores disponibles en el árbol estarán presentes en el intervalo de estos dos.

Una vez entendido el código anterior, este es muy similar, en este caso lo único que haremos será alterar el orden de los factores que en este caso, sí afectan el producto. Primero volveremos a llamar a la función para el hijo izquierdo cuando finalice o como explicado anteriormente, hayamos descargado las pesas de la barra, añadiremos el valor del propio nodo y finalizaremos repitiendo el paso inicial para el hijo derecho. Recordáis los casos iniciales que ponen tope a la recursividad, pues en este caso se llega cuando un nodo no tiene hijos por lo que únicamente añade su valor a la lista y descargamos su pesa para poder así descargar la siguiente.

2.3. Postorder traversal:

Como habrás deducido, este método busca priorizar ambos descendientes del nodo antes que el nodo. Este método en cuanto a búsqueda se usa en el rastreo de árboles que usan postfijos para su funcionamiento, sin embargo, la mayoría de veces que lo veremos relucir será cuando queramos eliminar un árbol o un tramo de dicho árbol. Esto es porque ambos hijos están priorizados antes que el nodo, y al igual que una casa no se empieza a construir por el tejado, un árbol no se empieza a destruir por el nodo.

No nos meteremos tanto en el funcionamiento del código ya que lo hemos explicado más a detalle en los ejemplos anteriores, lo único que destacaremos será que otra vez hemos cambiado el orden de las funciones. Podemos ver cómo llamamos a la función con el hijo izquierdo y el derecho antes de añadir el valor. La recursividad nos permite que una tarea tan compleja como podía parecer esta la hemos podido desarrollar con 3 códigos muy similares en los que únicamente cambiamos un par de líneas, haciendo que no sea tan necesario centrarnos en el código en sí, sino en el concepto. En caso de que quisiéramos hacer una limpieza del árbol en vez de la lectura de valores, sería tan simple como cambiar la línea 5 por nodo = None (así es como se asigna un valor nulo en Python).

2.4. Level-order traversal:

Hemos visto cómo movernos por un árbol, cómo leer el árbol entero de dos maneras dependiendo la funcionalidad que le queremos apretar y hasta hemos visto cómo eliminar un árbol. Ahora nos tocaría aprender a cultivarlo.

Para esto usaremos este último método, es un poco más distinto que los demás, una de las diferencias es que no se usa recursividad en su aplicación, sino una pila de datos, la diferencia es que el acceso por nodos no será LIFO (Last In First Out o último en entrar primero en salir), sino que será FIFO (First In First Out o primero en entrar primero en salir).

El código podemos ver que vamos añadiendo a la pila por la derecha los nodos que queremos mas tarde asignar a sus hijos y por la izquierda sacamos a los nodos que queremos asignar a sus hijos.

En este código la razón por la que no nos detendremos tanto es porque es conceptualmente más complejo y nuestra intención es entender los conceptos básicos relacionados con los árboles binarios, ya que hay decenas de tipos de colecciones y no podemos pararnos a analizar por qué es de gran utilidad como estructura para la pila, por su función popleft. Veamos visualmente cómo funcionará el código que nos será de gran ayuda para la comprensión de este método.

Referencias:

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.

2. Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.

3. Lafore, R. (2002). Data Structures and Algorithms in Java (2nd ed.). Sams Publishing.

 Artículo participante del VIII Concurso de Artículos de Divulgación Científica de la Universidad de Burgos.

Imagen inicial creada con herramientas de IA por la UCC+i UBU.