人工衛星

説明

アルファ・ケンタウリへ向かう衛星に二分木を送信する必要があり、しかも通信帯域が限られていると想像してみてください。 この木には重複する要素がないので、行きがけ順と通りがけ順の走査によって一意に表すことができます。

その走査結果から木を復元するソフトウェアを、衛星のために書きましょう。

行きがけ順の走査では、左部分木を行きがけ順で読む前に、現在のノードの値を読みます（だから「行きがけ」なのです）。 その後、右部分木を行きがけ順で読みます。

通りがけ順の走査では、左部分木を通りがけ順で読み、次に現在のノード、最後に右部分木を通りがけ順で読みます。 つまり、左から右へと順に読み進めることになります。

たとえば、この木の行きがけ順の走査は[a, i, x, f, r]です。 通りがけ順の走査は[i, a, f, x, r]です。

  a
 / \
i   x
   / \
  f   r

補足：行きがけ順の走査で最初に現れる要素は、常に根です。

この演習は、確定節文法（DGC）を使って実装してください。 DCGは、並び（配列）を解析するだけでなく、その並びを生成したり、補完したり、検査したりするのにも使えます。

ライブラリー

スタブの実装ファイルには、次の行が含まれています。

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

これでdcg/basicsライブラリーを利用できるようになります。この演習を解くには十分なはずです。

参考資料

PrologでDCGを始めるのに役立つ資料を以下に挙げます。

• metalevel.at
• wikipedia
• swipl