Tarea 5 de Almacenamiento y Recuperación de la Información

Trimestre 2013 Primavera
Entrega: 14 de junio de 2013 a las 22:00.

El propósito de esta tarea es el de practicar los conceptos de árboles 2-3-4 vistos en clase. Recuerde que un árbol es 2-3-4 si (1) todos los caminos de la raíz a las hojas tienen el mismo número de nodos y (2) cada nodo que no es hoja tiene 2, 3 o 4 hijos.

Escribe un programa arboldtcNN que decida si un árbol es 2-3-4 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 arboldtc.ent y consiste de un renglón con un entero N (la cantidad de nodos del árbol) seguido de N renglones con la información relativa a cada uno de los nodos 1, 2, ..., N. El renglón j comienza con un entero Tj que es el tipo del nodo j (Tj puede valer 2, 3 o 4 según el nodo j sea un 2-, 3- o 4-nodo) y continua con Tj enteros que corresponden con los números de sus hijos. En el caso de que falte un hijo esto se indicará con el número 0. Observa que el número del nodo no tiene ninguna relación con la clave o claves que contiene. Puedes suponer 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 arboldtc.sal y consiste de un renglón con un entero R (el número de la raiz si el árbol es 2-3-4 y 0 si no lo es). En el caso de que el árbol sea 2-3-4 el segundo renglón deberá contener la cantidad H de hojas del árbol y el tercer renglón deberá contener una lista con las H hojas del árbol (ordenadas de menor a mayor de acuerdo a su número de nodo). En el caso de que el árbol no sea 2-3-4 el segundo renglón deberá contener la cantidad V de hojas de T que violan la condición (1) y el tercer renglón deberá contener una lista con esas V hojas (ordenados de menor a mayor de acuerdo a su número de nodo).

Ejemplo

Entrada 1
 Salida 1
 Entrada 2
 Salida 2
12
2 6 8
2 11 9
3 1 5 2
2 0 0
4 4 7 12 10
3 0 0 0
2 0 0
4 0 0 0 0
2 0 0
2 0 0
2 0 0
2 0 0
 3
8
4 6 7 8 9 10 11 12
 6
3 0 0 0
2 0 0
3 1 5 2
2 0 0
2 4 6
2 0 0
 0
2
1 2