序言从左到右遍历非标准树

Question

我需要实现一个谓词 trav(Tree,List) 执行左到右树遍历；

其中：树由结构节点（左，右）定义，其中左和右可以是另一个节点或任何 Prolog 数据项。 List 是树中叶节点值的列表。

例如：

?- trav(x,L).
L = [x].
?- trav(node(1,node(2,node(a,b))),L).
L = [1, 2, a, b] .

我目前拥有的：

trav(tree,[ ]).
trav(node(Left,Rigth), L) :-
    trav(Left, L),
    trav(Right, L),
    append(Left,[Left|Right],L).

Answer 1

我的 Prolog 有点生疏了，但我相信应该这样做：

node(Left, Right).

trav(node(Left, Right), L) :- 
  trav(Left, L1), 
  trav(Right, L2),
  append(L1, L2, L).
trav(X, [X]) :- X \= node(A, B).

直观上，trav(Left, L1)表示遍历左子树，将每个元素存储在L1中。 trav(Right, L2)表示遍历存储L2中每个元素的右子树。最后，append(L1, L2, L) 将两个列表 L1 and L2 附加到列表 L 中。对于叶子，trav(X, [X])，将 X 放入单例列表中，只要它不与 node 统一。

序言从左到右遍历非标准树

prolog traverse nonstandard tree left to right

tree

prolog

tree-traversal