Satellit

Anleitung

Stell dir vor, du musst einen Binärbaum zu einem Satelliten übertragen, der sich Alpha Centauri nähert, und du hast nur eine begrenzte Bandbreite. Da der Baum keine wiederholten Elemente enthält, lässt er sich eindeutig durch seine Preorder- und Inorder-Traversierung darstellen.

Schreibe die Software für den Satelliten, damit er den Baum aus den Traversierungen rekonstruiert.

Eine Preorder-Traversierung liest den Wert des aktuellen Knotens, bevor (daher „pre“) sie den linken Teilbaum in Preorder liest. Danach wird der rechte Teilbaum in Preorder gelesen.

Eine Inorder-Traversierung liest zuerst den linken Teilbaum in Inorder, dann den aktuellen Knoten und schließlich den rechten Teilbaum in Inorder. Also in der Reihenfolge von links nach rechts.

Zum Beispiel ist die Preorder-Traversierung dieses Baums [a, i, x, f, r]. Die Inorder-Traversierung dieses Baums ist [i, a, f, x, r]

  a
 / \
i   x
   / \
  f   r

Hinweis: Das erste Element der Preorder-Traversierung ist immer die Wurzel.

Du solltest diese Übung mit einer Definite Clause Grammar (DGC) umsetzen. DCGs kann man nicht nur verwenden, um Sequenzen (Listen) zu parsen, sondern auch, um diese Sequenzen zu erzeugen, zu vervollständigen und zu prüfen.

Bibliothek

Die Stub-Implementierungsdateien enthalten die folgende Zeile:

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

Damit stellst du sicher, dass die Bibliothek dcg/basics verwendet werden kann, was ausreichen sollte, um diese Übung zu lösen.

Ressourcen

Die folgenden Ressourcen helfen dir beim Einstieg in DCGs in Prolog:

• metalevel.at
• Wikipedia
• swipl