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

Trimestre 2009 Invierno
Entrega: 11 de marzo a las 22:00.

El propósito de esta tarea es el de practicar los conceptos de árboles rojinegros vistos en clase.

Sea T = (V, E) un árbol binario con nodos rojos y negros. Recuerde que T es un árbol rojinegro si (1) la raíz es negra, (2) ningún nodo rojo es hijo de otro nodo rojo y (3) todos los caminos de la raíz a las hojas tienen el mismo número de nodos negros.

Escribe un programa rojinegroNN que decida si un árbol binario es rojinegro 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 rojinegro.ent y consiste de un renglón con un entero N (la cantidad de nodos de T) seguido de N renglones con tres enteros Cj, Xj y Yj, donde Cj es el color del nodo j (0 es negro y 1 es rojo), 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). Observa que la clave almacenada en el nodo j es desconocida. 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 rojinegro.sal y consiste de un renglón con un entero R (1 si T es rojinegro y 0 si no lo es). En el caso de que R sea rojinegro 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 rojinegro el segundo renglón deberá contener la cantidad V de nodos de T que violan la condición (2) y el tercer renglón deberá contener una lista con esos V nodos (ordenados de menor a mayor).

Ejemplo

Entrada 1
Salida 1
Entrada 2
Salida 2
7
0 0 0
1 1 5
1 0 0
1 0 0
0 4 3
0 7 2
0 0 0
1
4
1 3 4 7
7
1 0 0
1 1 5
1 0 0
0 0 0
1 4 3
0 7 2
0 0 0
0
3
1 3 5