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.
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.
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)):
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.