卫星

说明

想象一下，你需要把一棵二叉树传输给一艘正在飞向半人马座α的卫星，而带宽十分有限。 由于树中没有重复的元素，因此可以用它的前序遍历和中序遍历来唯一地表示。

为卫星编写软件，让它根据这些遍历结果重建这棵树。

前序遍历会先（也就是“前”）读取当前节点的值，再按前序读取左子树。 之后按前序读取右子树。

中序遍历会先按中序读取左子树，然后读取当前节点，最后按中序读取右子树。 也就是从左到右依次读取。

例如，这棵树的前序遍历是 [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