Semana 7 - Recorridos en árboles binarios

✔️ Objetivos

Distinguir los distintos tipos de recorridos en un árbol binario: preorden, inorden, postorden y recorrido en anchura.
Saber implementar, de manera recursiva, los recorridos en profundidad: preorden, inorden y postorden.
Saber implementar, de manera iterativa, el recorrido en anchura de un árbol utilizando una cola auxiliar.
Utilizar objetos función y expresiones lambda para definir las acciones a realizar en el recorrido de un árbol.

✔️ Tiempo de estudio

Vídeos: 47min
Total (incluyendo vídeos, cuestionarios y actividades de autoevaluación, pero no los problemas de la sección 7.4): 2h

7.1. Recorriendo un árbol binario

Ya sabéis cómo recorrer listas utilizando iteradores. ¿Y si quisiéramos recorrer un árbol? El problema aquí es más complejo, ya que los árboles son estructuras no lineales y el orden en el que pueden visitarse los nodos no resulta tan obvio como en el caso de una lista.

Dedicaremos esta semana a los tipos de recorridos más habituales en un árbol. El siguiente vídeo es el más importante de esta semana. En él se describen los tipos de recorridos que vamos a estudiar durante este curso.

▶️ Recorridos de árboles binarios (7:41)

📝 Ejercicio 7.1

¿Has entendido la diferencia entre los recorridos? En el siguiente test puedes practicarlos:

❓ Cuestionario de autoevaluación - Recorridos en árboles binarios

7.2. Una primera implementación de los recorridos en un árbol

Conocidos los conceptos relativos a los recorridos, vamos a comenzar con las implementaciones. Para facilitar las cosas, supondremos que la operación de visitar un nodo consiste, simplemente, en imprimir su contenido.

La implementación de los recorridos en profundidad es bastante sencilla si se aborda con un diseño recursivo:

▶️ Implementación de recorridos en profundidad (DFS) (3:25)

La implementación de los recorridos en anchura se complica un poco más, debido al hecho de que utiliza una cola auxiliar. No obstante, la idea siendo bastante intuitiva. Además, para este recorrido no hace falta recursión:

▶️ Implementación de recorridos en anchura (BFS) (4:11)

📄 Código fuente

7.3. Redefiniendo la acción de visitar: funciones de orden superior

Comencemos con un sencillo ejercicio:

📝 Ejercicio 7.2

Nuestra definición de inorder hace un recorrido en inorden de un árbol binario, imprimiendo el valor de cada nodo a medida que pasaba por él. En el siguiente ejercicio, modifica el método inorder para que reciba dos parámetros adicionales:

after (de tipo string) - Indica la cadena que debe imprimirse tras el contenido de cada elemento. Debe sustituir al espacio en blanco (" ") que imprime la versión actual de inorder.
min_value (de tipo const T &) - Indica un valor umbral mínimo que ha de tener un elemento para que se muestre por pantalla. Los nodos del árbol cuyo valor sea menor que min_value no serán mostrados.

💻 Ejercicio: parametrizar el método inorder

💻 Solución

Con este ejercicio hemos conseguido personalizar ligeramente las acciones a realizar en cada nodo durante el recorrido, pero, aun así, hay mucho margen de mejora. ¿Y si quisiéramos hacer otra cosa que no sea, simplemente, imprimir el nodo por pantalla? Sería muy complicado (y absurdo) tener un método inorder distinto para cada tipo de acción que queramos hacer sobre un árbol. El objetivo de esta sección es modificar los métodos preorder, inorder y postorder para que reciban como parámetro una función que implemente la acción a realizar para cada nodo.

Pero, ¿es posible pasar una función como parámetro en C++? Sí, es posible.

Las funciones de C++ pueden asignarse a variables, pueden pasarse por parámetro, o incluso devolverse como resultado. Los lenguajes de programación que permiten todo esto reciben el nombre de lenguajes de orden superior.

Vamos a ver cómo funcionan las funciones de orden superior en un sencillo ejemplo con listas. Antes de comenzar con el siguiente vídeo, conviene que repases el primer ejercicio de la hoja que vimos hace un par de semanas (Recorridos con iteradores). En particular, echa un vistazo a la función eliminar_pares.

▶️ C++ - Funciones de orden superior (7:37)

📄 Código fuente

Antes de seguir, vamos a poner en práctica la nueva función eliminar con algunos ejemplos, que también servirán para motivar el vídeo que viene después.

📝 Ejercicio 7.3

Dada una lista de nombres recibida por teclado, utiliza la función eliminar para eliminar aquellos nombres que comiencen por la letra A.

💻 Ejercicio: eliminar nombres que comiencen por la letra A

💻 Solución

📝 Ejercicio 7.4

Dada una lista de nombres recibida por teclado, utiliza la función eliminar para eliminar aquellos nombres que comiencen por la letra que indique el usuario a través de la entrada.

💻 Ejercicio: eliminar nombres que comiencen por la letra indicada por el usuario

¿Has conseguido resolver este último? Es más difícil, porque la función que se pasa como parámetro depende de la letra introducida por el usuario. No obstante, el ejercicio se puede resolver con los mecanismos que hemos visto en el vídeo anterior. A continuación se muestra una posible solución, aunque podría no gustarte:

💻 Solución: eliminar nombres que comiencen por la letra indicada por el usuario

¡Aggg! ¿Eso era una variable global?. Sí, pero tenemos suerte, porque los objetos función, que veremos a continuación, permiten librarnos de esta variable:

▶️ C++ - Objetos función (11:57)

📄 Código fuente

📝 Ejercicio 7.5

Intenta ahora resolver el problema anterior, pero utilizando objetos función:

💻 Ejercicio: eliminar nombres que comiencen por la letra indicada por el usuario

💻 Solución

Con los objetos función hemos conseguido lo que queríamos, pero sin hacer uso variables globales. No obstante, hemos tenido que crear una clase adicional para implementar la sobrecarga del operador (). A continuación presentamos las expresiones lambda, que permiten declarar objetos función «de usar y tirar»:

▶️ C++ - Expresiones lambda (7:29)

📄 Código fuente

📝 Ejercicio 7.6

A continuación, modifica la solución del ejercicio anterior sustituyendo el objeto función por una expresión lambda:

💻 Ejercicio: expresiones lambda para eliminar nombres comiencen por la letra indicada por el usuario

💻 Solución

Todo lo que ha venido en esta sección ha sido bastante denso. Vamos a aplicarlo al tema que hemos estado tratando esta semana: los recorridos en un árbol.

▶️ Parametrizando el recorrido de un árbol (5:19)

📄 Código fuente

📝 Ejercicio 7.7

Finalizamos con un test de autoevaluación sobre la implementación de recorridos:

❓ Cuestionario de autoevaluación - Implementación de los recorridos de un árbol