Taller 6

Objetivos

  • Practicar la construcción de árboles dadas ciertas restricciones
  • Aprender uno de los usos del árbol binario

Problema: Reconstruir un árbol

En lel texto guía del curso encontrará la información sobre diferentes tipos de recorrido que se pueden aplicar en un árbol binario.

Es importante notar que varios árboles diferentes pueden resultar en la misma cadena de elementos al imprimirlos con el mismo tipo de recorrido.

Por ejemplo, las llaves de este árbol[1](#ref1):

ordenadas con el recorrido de inorden, luce así:

A, C, E, H, M, R, S, X

Y las de este otro árbol[2](#ref2):

lucen igual.

Para determinar cómo era el orden orginal del árbol, sería necesario saber el orden en el que se agregaron los elementos, o en su defecto, conocer también la cadena resultante de un recorrido de preorden.

En este taller se desea que cree un algoritmo que, dadas dos listas que definen el inorden y preorden de un árbol, retorne el original, teniendo en cuenta que ninguno de los elementos del árbol está repetido.

El esqueleto del taller lo puede encontrar en este link.

  1. La aplicación debe leer la información de un archivo properties que se encuentre en la carpeta data. En el esqueleto, puede encontrar un ejemplo. Cree el método que lee este archivo y almacena el preorden y el inorden del árbol a construir.

  2. Cree una estructura de datos de árbol binario simple, donde pueda asignar los nodos izquierdo y derecho a su conveniencia (no puede ser un ABO).

  3. Ahora, debe crear el método que reconstruye el árbol. Utilice su estructura de datos para guardarlo. En el problema se asume que el preorden y posorden son atributos del mundo. No tenga en cuenta casos en los que sea imposible reconstruir el árbol (por ejemplo, que sean recorridos de árboles diferentes). Asuma que el inorden y preorden son correctos y pertenecen al mismo árbol.

  4. Una vez tenga el árbol, debe crear el método que imprime el árbol en formato JSON. Cada nodo debe tener un valor y si existen, un hijo derecho y un hijo izquierdo.

  5. Por último, cree el método crearArchivo para generar el archivo de texto con el árbol. Si desea visualizar su árbol para revisar que haya quedado bien construido, puede ir al siguiente link y copiar el contenido de su archivo.

Para probarlo, basta con que cree un árbol, y construya las cadenas de inorden y preorden de ese árbol, cree un nuevo archivo properties, y corra su aplicación.

Preguntas

¿Es posible lograr el mismo resultado con el preorden y posorden? ¿Con el inorden y posorden?

Reto(opcional)

Implemente un algoritmo que detecte si un árbol contiene un subárbol dado.

Entrega para bonificación

Fecha límite de entrega: Ver

  1. Verifique que su aplicación cumple con las condiciones descritas en Envío talleres.
  2. Conteste las preguntas en el archivo README.txt.
  3. Realice pruebas unitarias para la aplicación de siembra de árboles las cuales se deben encontrar en el paquete taller.test. Como mínimo sus pruebas deberían validar los casos que puede encontrar en este link, y otras pruebas que considere pertinentes.
  4. Modifique su aplicación para que permita nombrar el archivo donde se guardará el árbol plantado.
  5. Cargue el taller a su repositorio en Bitbucket. No olvide crear el archivo calificacion.txt

Referencias

1: Sedgewick, Robert y Kevin Wayne. Algorithms 4th ed. Pearson Education, 2011.

2: Ídib