Műhold

Utasítások

Képzeld el, hogy egy bináris fát kell átküldened egy műholdra, amely az Alpha Centauri felé közeledik, és korlátozott a sávszélességed. Mivel a fában nincsenek ismétlődő elemek, egyértelműen reprezentálható a preorder és inorder bejárásaival.

Írd meg a szoftvert a műholdnak, hogy a bejárásokból újraépítse a fát.

A preorder bejárás előbb beolvassa az aktuális csúcs értékét, mielőtt a bal részfát preorder módon bejárná (innen a „pre” elnevezés). Ezután a jobb részfa preorder bejárása következik.

Az inorder bejárás először a bal részfát járja be inorder módon, majd az aktuális csúcsot olvassa be, végül pedig a jobb részfát is inorder módon. Tehát balról jobbra haladva.

Például ennek a fának a preorder bejárása: [a, i, x, f, r]. Az inorder bejárása pedig: [i, a, f, x, r]

  a
 / \
i   x
   / \
  f   r

Megjegyzés: a preorder bejárás első eleme mindig a gyökér.

Ezt a feladatot határozott klóznyelvtan (definite clause grammar, DGC) segítségével érdemes megvalósítanod. A DCG-k nemcsak sorozatok (listák) elemzésére használhatók, hanem ilyen sorozatok előállítására, kiegészítésére és ellenőrzésére is.

Könyvtár

A vázmegvalósítás fájljai a következő sort tartalmazzák:

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

Ez biztosítja, hogy a dcg/basics könyvtárat használhasd, ami elégnek kell lennie a feladat megoldásához.

Források

Az alábbi források hasznosak lehetnek, ha elkezdenél DCG-kkel dolgozni Prologban:

• metalevel.at
• Wikipédia
• swipl