在 Prolog 中查找二叉树偶数层的元素

Question

我试图在二叉树中找到所有放置在偶数层的元素并将它们放入列表中。这是我试过的：

concat([],L,L).
concat([H|T], L, [L|LRez]) :- concat(T,L,LRez).

find(R, t(_, R, _), 0).
find(X, t(S, R, D),P) :- X < R, find(X, S, P1), P is P1+1.
find(X, t(S, R, D),P) :- X >= R,find(X, D, P2), P is P2+1.

level(T, LRrez):- lvl(T, T, LRez).
lvl(nil, nil, []).
lvl(T, t(S,R,D),[R|LRez] ) :- find(R,T,P), even(P), lvl(T, S, LRez1), lvl(T,D,LRez2), 
                        concat(LRez1,LRez2,Lrez).
lvl(T,t(S,R,D),LRez) :- find(R,T,P), \+even(P), lvl(T, S, LRez1), lvl(T, D,LRez2), 
                        concat(LRez1,LRez2,Lrez).

我使用 find 来查找树中数字的级别，我什至在之前定义过。这是行不通的。提前致谢。

Answer 1

使用dcg!

如果您不熟悉 DCG，请阅读 Markus Triska's informative yet concise DCG Primer。

take_even(nil)      --> [].
take_even(t(L,M,R)) --> [M], skip_odd(L), skip_odd(R).

skip_odd(nil)      --> [].
skip_odd(t(L,_,R)) --> take_even(L), take_even(R).

示例查询：

?- phrase(take_even(t(nil,0,t(nil,1,t(nil,2,nil)))), Es).
Es = [0, 2].

在 Prolog 中查找二叉树偶数层的元素

Find the elements on even level of a binary tree in Prolog

binary-tree

list

prolog

dcg