使用 var(X) 的 Prolog 二叉树

Question

我构建了二叉树结构，binarytree(Data,LeftSub,RightSub)。

istree(nil).
istree(binarytree(_,L,R)) :- istree(L), istree(R).

但是，我想用未实例化的变量而不是 istree(nil) 来表示空树，使用内置谓词 var(X)。

istree(D) :- var(D).
istree(binarytree(D,_,_)) :- var(D).
istree(binarytree(D,L,R)) :- not(var(D)).
istree(binarytree(D,L,R)) :- not(var(D)), istree(L), istree(R).

我试过了，好像不太对。

Answer 1

同时断言一组子句的真假可能会出现问题。我认为你可以只陈述正面案例，否则让 Prolog 失败：

istree(T) :-
    nonvar(T),
    T = t(_,L,R),
    (var(L) ; istree(L)),
    (var(R) ; istree(R)).

我缩短了仿函数，以简化测试

8 ?- istree(t(a,_,_)).
true 
.

9 ?- istree(t(a,t(b,_,_),_)).
true 
.

10 ?- istree(t(a,t(b,_,_),t(c,_,_))).
true 
.

使用 var(X) 的 Prolog 二叉树

Prolog binary tree using var(X)

prolog