Satélite

Instrucciones

Imagina que tienes que transmitir un árbol binario a un satélite que se aproxima a Alfa Centauri y que dispones de un ancho de banda limitado. Como el árbol no tiene elementos repetidos, se puede representar de forma única mediante sus recorridos en preorden y en inorden.

Escribe el software del satélite para reconstruir el árbol a partir de los recorridos.

Un recorrido en preorden lee el valor del nodo actual antes (de ahí el «pre») de leer el subárbol izquierdo en preorden. Después se lee el subárbol derecho en preorden.

Un recorrido en inorden lee el subárbol izquierdo en inorden, luego el nodo actual y, por último, el subárbol derecho en inorden. Es decir, en orden de izquierda a derecha.

Por ejemplo, el recorrido en preorden de este árbol es [a, i, x, f, r]. El recorrido en inorden de este árbol es [i, a, f, x, r].

  a
 / \
i   x
   / \
  f   r

Nota: el primer elemento del recorrido en preorden es siempre la raíz.

Deberías implementar este ejercicio usando una gramática de cláusulas definidas (DCG). Las DCG no solo sirven para analizar secuencias (arrays), también pueden generarlas, completarlas y comprobarlas.

Biblioteca

Los archivos de implementación del esqueleto incluyen la siguiente línea:

:- use_module(library(dcg/basics)).

Esto garantiza que se pueda usar la biblioteca dcg/basics, lo cual debería bastar para resolver este ejercicio.

Recursos

Estos son algunos recursos útiles para empezar con las DCG en Prolog:

• metalevel.at
• wikipedia
• swipl