衛星

說明

想像一下，你需要把一棵二元樹傳送到正在接近 Alpha Centauri 的衛星上，而你的頻寬有限。 這棵樹沒有重複的項目，因此可以由它的前序與中序走訪唯一表示。

請為衛星撰寫軟體，根據這些走訪結果重建這棵樹。

前序走訪會先讀取目前節點的值（因此稱為「pre」），再以前序走訪左子樹。 接著同樣以前序走訪右子樹。

中序走訪會先以中序走訪左子樹，再讀取目前節點，最後以中序走訪右子樹。 也就是由左到右的順序。

例如，這棵樹的前序走訪是 [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
• 維基百科
• swipl