Prolog 中的树

Question

我正在研究 Prolog 中的二叉树。

我知道结构，但我不明白幻灯片中的这段代码：

binary_tree(void).
binary_tree(tree(_Element,Left,Right)) :-
  binary_tree(Left), binary_tree(Right).

这需要识别树结构。

但是"void"代表什么？

我试过这个查询

?- binary_tree(a).
false.

并假设 a 是树的一个节点。

我正在关注此资源以了解：

https://sites.google.com/site/prologsite/prolog-problems/4

但与我的幻灯片不同。

谁能澄清一下？

Answer 1

void 是一个原子。它不能假定任何值（除了它自己）。此外，a 也是一个原子，根据您的谓词定义，它不是有效的树。以 a 作为其唯一节点的树将由复合术语 tree(a,void,void):

表示

| ?- binary_tree(tree(a,void,void)).

yes

再举一个例子，一棵节点为 a..g 的平衡树将由以下术语表示（缩进只是为了便于阅读）：

   tree(a,
       tree(b,
           tree(d,void,void),
           tree(e,void,void)
       ),
       tree(c,
           tree(f,void,void),
           tree(g,void,void)
       )
    )

您可以再次使用您的 binary_tree /1 谓词验证此术语是否为树：

| ?- binary_tree(tree(a,tree(b,tree(d,void,void),tree(e,void,void)),tree(c,tree(f,void,void),tree(g,void,void)))).

yes

Prolog 中的树

Trees in Prolog

tree

prolog

first-order-logic