Satélite

Instruções

Imagina que precisas de transmitir uma árvore binária para um satélite a aproximar-se de Alpha Centauri e tens largura de banda limitada. Como a árvore não tem itens repetidos, pode ser representada de forma única pelos seus percursos em pré-ordem e em ordem.

Escreve o software do satélite para reconstruir a árvore a partir dos percursos.

Um percurso em pré-ordem lê o valor do nó atual antes (daí o "pré") de ler a subárvore esquerda em pré-ordem. A seguir, a subárvore direita é lida em pré-ordem.

Um percurso em ordem lê a subárvore esquerda em ordem, depois o nó atual e, por fim, a subárvore direita em ordem. Ou seja, da esquerda para a direita.

Por exemplo, o percurso em pré-ordem desta árvore é [a, i, x, f, r]. O percurso em ordem desta árvore é [i, a, f, x, r]

  a
 / \
i   x
   / \
  f   r

Nota: o primeiro item do percurso em pré-ordem é sempre a raiz.

Deves implementar este exercício recorrendo a uma gramática de cláusulas definidas (DCG). As DCG podem ser usadas não só para analisar sequências (listas), mas também para gerar, completar e verificar essas sequências.

Biblioteca

Os ficheiros stub da implementação incluem a seguinte linha:

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

Esta linha garante que podes usar a biblioteca dcg/basics, o que deve ser suficiente para resolveres este exercício.

Recursos

Estes recursos são úteis para começares a trabalhar com DCG em Prolog:

• metalevel.at
• wikipedia
• swipl