Tarea 3 de Almacenamiento y Recuperación de la
Información
Trimestre 2008 Invierno
Entrega: 6 de mayo 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.
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-1 renglones con dos enteros
Xj y Yj (las aristas de T), donde Xj < Yj y Yj es hijo de Xj. Puedes
suponer 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).