二叉树的 Prolog 验证

Question

我是 prolog 的初学者，我想编写一个谓词，如果参数是树，则该谓词变为真。我有这段代码，但它总是给我错。谁能帮帮我。

arb_true(nil).
arb_true([X,G,D]):- X=[_,G,D], arb_true(G), arb_true(D).

查询是arb_true([6,[4,[1,[],[]],[]],[9,[],[]]]).

Answer 1

您已经定义了子句 arb_true(nil). 但您用空列表而不是 'nil' 表示空树，所以您需要写：

arb_true([]).

你还需要写：

arb_true([_,G,D]):-arb_true(G), arb_true(D).

而不是：

arb_true([X,G,D]):- X=[_,G,D], arb_true(G), arb_true(D).

正在查询 arb_true([6,[4,[1,[],[]],[]],[9,[],[]]]). :

 ?- arb_true([6,[4,[1,[],[]],[]],[9,[],[]]]).
true.

Answer 2

通常，您不会将树表示为三个元素的列表，而是具有三个参数的术语。无论您决定以何种方式表示一棵树，都需要保持一致。在您当前的（我假设不起作用？）解决方案中，您很好地混合了两种不同的方式来表示一棵树。

这是表示二叉树的一种方法：空树是原子 nil，非空树是项 tree(Value, Left, Right)。所以：

binary_tree(nil).
binary_tree(t(_, L, R)) :-
    binary_tree(L),
    binary_tree(R).

或者，如果您选择使用包含三个元素的列表 [Value, Left, Right]，并将空列表 [] 作为空树，您将拥有：

binary_tree([]).
binary_tree([_, L, R]) :-
    binary_tree(L),
    binary_tree(R).

我会说第一种表现形式更常见。在这两种情况下，如果您只想检查它是否是二叉树，您可以（并且应该）忽略 "value"（tree(Value, Left, Right) 中的第一个参数或 [Value, Left, Right] 中的第一个元素.

但是：你的例子显示了一个二叉三，它也是一个排序的二叉树，或者一个binary search tree。要验证您是否拥有它，您需要比较左右子树中的实际值。这目前不是您问题的一部分，因此您需要使用必要的详细信息对其进行编辑。

Prolog verification of a binary trees