Satélite

Instruções

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

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

Um percurso pré-ordem lê o valor do nó atual antes (daí o "pré") de ler a subárvore esquerda em pré-ordem. Em seguida, 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 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

Observação: o primeiro item do percurso pré-ordem é sempre a raiz.

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

Biblioteca

Os arquivos stub de implementação incluem a seguinte linha:

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

Isso garante que a biblioteca dcg/basics possa ser usada, o que deve ser suficiente para resolver este exercício.

Recursos

A seguir estão alguns recursos úteis para começar com DCGs em Prolog:

• metalevel.at
• wikipedia
• swipl