Ejercicios · Estructuras C23¶
Árboles y árboles binarios, la recursión sobre ellos y los tres recorridos, con recursión y con pila. Cada enlace abre una actividad que se trabaja directo en el navegador, en el mismo orden de los temas de la sesión. Los árboles y los programas no son los de la sesión: mismo tema, ronda nueva.
Datos que se contienen unos a otros¶
contener¶
Un organigrama guardado en una lista: dos organigramas distintos que dan la misma lista y lo que cuesta preguntar qué depende de Producción.
El TAD árbol¶
terminologia¶
Padre, hermanos, grado, profundidad, altura y niveles en un árbol de once
nodos, y cuántos punteros quedan en NULL al guardarlo con primer hijo y
hermano siguiente.
El árbol binario¶
vacios¶
Un árbol de nueve nodos armado con crearNodo: cuántos vacíos tiene, cuántos
hay con mil nodos y qué cambia al pasar un hijo como izquierdo en vez de
derecho.
La recursión, desde el árbol¶
llamadas¶
contarPares sobre un árbol de cinco nodos: lo que devuelve cada llamada, la
pila de llamadas marco por marco y cuántos marcos conviven.
casobase¶
Cuatro versiones del producto de los datos que solo cambian en el caso base: una da siempre 0, una acierta y dos se caen. Al final, la altura con el vacío en 0.
Recorridos: preorden, inorden y posorden¶
predecir¶
Los tres recorridos de un árbol de nueve nodos, escritos antes de verlos numerados, y qué árbol tiene el preorden igual al inorden.
expresion¶
El árbol de (9 - 4) * 2 - 12 / (1 + 3): notación prefija y postfija, lo que
devuelve cada operador, la postfija evaluada con una pila y lo que da la cadena
sin paréntesis.
Recorridos con pila explícita¶
pila¶
preordenPila, inordenPila y posordenPila vuelta por vuelta sobre un
árbol de siete nodos, y la versión que apila los hijos al revés. Es de las más
largas de la página.
Liberar el árbol¶
liberar¶
En qué orden borra liberar y qué falla en tres versiones que hacen el
delete antes de terminar con el nodo.
Para el juez¶
reconstruir¶
Un árbol de ocho nodos rehecho a partir de su preorden y su inorden, rango por rango, con su posorden; y por qué el preorden con el posorden no alcanzan. Es la más exigente de la página.
columnas¶
Un árbol que llega en preorden con −1 en cada vacío, como en UVa 699: cuántos nodos trae, en qué columna cae cada uno y qué sumas se imprimen.
Lo que cuesta¶
costos¶
Llamadas, altura y marcos de la pila en un árbol lleno y en uno degenerado con los mismos nodos, y cuál de los dos se cae con una pila de 1 MB.