Satellite

Istruzioni

Immagina di dover trasmettere un albero binario a un satellite che si avvicina ad Alpha Centauri, con una larghezza di banda limitata. Dato che l'albero non ha elementi ripetuti, può essere rappresentato in modo univoco dai suoi attraversamenti in pre-ordine e in ordine.

Scrivi il software che permetterà al satellite di ricostruire l'albero a partire dagli attraversamenti.

Un attraversamento in pre-ordine legge il valore del nodo corrente prima (da cui il «pre») di leggere il sottoalbero sinistro in pre-ordine. Subito dopo, il sottoalbero destro viene letto in pre-ordine.

Un attraversamento in ordine legge il sottoalbero sinistro in ordine, poi il nodo corrente e infine il sottoalbero destro in ordine. Quindi in ordine da sinistra a destra.

Ad esempio, l'attraversamento in pre-ordine di questo albero è [a, i, x, f, r]. L'attraversamento in ordine di questo albero è [i, a, f, x, r]

  a
 / \
i   x
   / \
  f   r

Nota: il primo elemento dell'attraversamento in pre-ordine è sempre la radice.

Per questo esercizio, usa una grammatica a clausole definite (DGC). Le DGC non servono solo ad analizzare sequenze (liste), ma anche a generarle, completarle e verificarle.

Libreria

I file stub dell'implementazione contengono la seguente riga:

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

Questo garantisce che la libreria dcg/basics possa essere utilizzata, e dovrebbe bastare per risolvere questo esercizio.

Risorse

Queste sono alcune risorse utili per iniziare con i DCG in Prolog:

• metalevel.at
• wikipedia
• swipl