Satellite

Instructions

Imagine que tu doives transmettre un arbre binaire à un satellite qui s'approche d'Alpha Centauri, avec une bande passante limitée. Comme l'arbre ne contient aucun élément en double, il peut être représenté de façon unique par ses parcours préfixe et infixe.

Écris le logiciel qui permettra au satellite de reconstruire l'arbre à partir de ces parcours.

Un parcours préfixe lit la valeur du nœud courant avant (d'où le « pré ») de parcourir le sous-arbre gauche en préfixe. Ensuite, le sous-arbre droit est parcouru en préfixe.

Un parcours infixe parcourt le sous-arbre gauche en infixe, puis le nœud courant, et enfin le sous-arbre droit en infixe. Donc, de gauche à droite.

Par exemple, le parcours préfixe de cet arbre est [a, i, x, f, r]. Le parcours infixe de cet arbre est [i, a, f, x, r]

  a
 / \
i   x
   / \
  f   r

Remarque : le premier élément du parcours préfixe est toujours la racine.

Tu dois implémenter cet exercice à l'aide d'une grammaire de clauses définies (DCG). Les DCG servent non seulement à analyser des séquences (des listes), mais aussi à les générer, à les compléter et à les vérifier.

Bibliothèque

Les fichiers d'implémentation fournis contiennent la ligne suivante :

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

Cela permet d'utiliser la bibliothèque dcg/basics, ce qui devrait suffire pour résoudre cet exercice.

Ressources

Voici quelques ressources utiles pour débuter avec les DCG en Prolog :

• metalevel.at
• wikipedia
• swipl