Tarea 4 de Almacenamiento y Recuperación de la
Información
Trimestre 2008 Primavera
Entrega: 8 de agosto de
2008 a las 22:00.
Sea T = (V,E) un árbol binario. Recuerde que T es un
árbol AVL si las alturas de los dos subárboles de cada
nodo difieren a lo mucho en 1.
Escribe un programa arbolavlNN
que decida si un árbol binario es AVL o no, donde NN son los dos
dígitos de la
clave que le fue proporcionada por el profesor. Página de prueba.
La entrada al programa estará en el archivo arbolavl.ent y consiste de un
renglón con un entero N (la cantidad de nodos de T) seguido de
N renglones con dos enteros
Xj y Yj, donde Xj y Yj son
los hijos izquierdo y derecho del nodo j (si alguno de Xj o Yj
vale 0 eso significa que el hijo correspondiente no existe). Puedes
suponer que T es un árbol binario, que los nodos de T
están numerados del 1 al N y que 1 <= N <= 100.
La salida del programa deberá estar en el archivo arbolavl.sal y consiste de un
renglón con un entero R (1 si T es AVL y 0 si no lo es).
En el caso de que R sea AVL
el segundo renglón deberá contener la cantidad H de hojas
de T y el tercer renglón deberá contener
una lista con las H hojas de T (ordenadas de menor a mayor).
En el caso de que R no sea AVL
el segundo renglón deberá contener la cantidad V de nodos
de T que violan la condición AVL y el tercer renglón
deberá contener
una lista con esos V nodos (ordenados de menor a mayor).