← Volver a los ejercicios

recorrido: en qué orden cierra cada nodo

listaEnteros descompone el conjunto con match y arma la lista con tres partes: listaEnteros(izq), List(elm) y listaEnteros(der). Un nodo cierra cuando construye su List(elm), es decir cuando aporta su elemento a la lista. Diga en qué lugar cierra cada uno de los siete nodos y qué lista sale al final.

1. La función y el conjunto

paso 0 de 0
lista acumulada: List()
■ línea 6: el subárbol izquierdo ■ línea 7: el elemento del nodo ■ línea 8: el subárbol derecho

Los cuadros grises son los conjuntos vacíos: cada nodo lleva dos hijos y los que no apuntan a otro nodo apuntan a Vacio(). Las líneas numeradas del código llevan contador con las veces que se evaluaron. Los botones quedan disponibles cuando la tabla y la predicción estén resueltas.

2. El orden de cierre

Los nodos están en el orden en que aparecen escritos en conjA. Asigne a cada uno el lugar en que aporta su elemento, de 1 a 7.

Y la lista que imprime println(listaEnteros(conjA)):

3. Lo que se lleva de aquí

El caso NoVacio(elm, izq, der) liga de una sola vez las tres partes del nodo, y el cuerpo las vuelve a juntar en el orden en que están escritas: primero la lista del subárbol izquierdo, después el elemento, después la del derecho. Esa escritura es todo el recorrido. La llamada de la línea 6 tiene que devolver antes de que se construya List(elm), así que todos los nodos del subárbol izquierdo aportan antes que el nodo que los contiene, y los del derecho después.

Sobre un árbol binario ordenado eso basta para que la lista salga ordenada: en cada nodo, lo que está a la izquierda es menor que el elemento y lo que está a la derecha es mayor, y el recorrido los pide en ese mismo orden. Mover List(elm) al principio del cuerpo cambiaría el recorrido y la lista dejaría de estar ordenada, sin tocar ni un dato del árbol.

Los contadores dicen lo demás. listaEnteros se llamó una vez por cada nodo y una vez por cada conjunto vacío: siete nodos, ocho vacíos, quince llamadas en total para una lista de siete elementos. La función está escrita por fuera de la jerarquía, sin agregar un método a Vacio ni a NoVacio: match es lo que le deja ver por dentro las dos formas del conjunto.