prolog - Prolog中的树前序遍历

Question

树遍历是指系统地访问树数据结构中的每个节点的过程。下图中的前序遍历

排序二进制树

返回 F、B、A、D、C、E、G、I、H（根、左、右）。这是序言代码：

preorder(tree(X,L,R),Xs) :-
    preorder(L,Ls),
    preorder(R,Rs),
    append([X|Ls],Rs,Xs).
preorder(void,[]).

我会写一个序言程序返回

F，B，A，F，B，D，C，F，B，D，E，F，G，I，H

也就是树的路径。有什么建议么？

Answer 1

在将当前节点传递给左/右访问者之前，在当前节点的PathToRoot位置添加一个参数。

叶谓词将在返回之前将接收到的累加器与其相反的累加器统一起来。

根调用将有一个空的累加器。

Answer 2

试试这个尺寸：

dfs_paths(tree(X, void, void), [X]) :- !.
dfs_paths(tree(X, L, _R), [X|Xs]) :-
    dfs_paths(L, Xs).
dfs_paths(tree(X, _L, R), [X|Xs]) :-
    dfs_paths(R, Xs).

从这里用代表树的事实对其进行测试：

tree(T) :- T = tree(f, tree(b, tree(a,void,void), tree(d,tree(c,void,void),tree(e,void,void))), tree(g, void, tree(i, tree(h,void,void),void))).

尝试一下（不显示绑定T）：

?- tree(T), dfs_paths(T, L).
L = [f, b, a] ;
L = [f, b, d, c] ;
L = [f, b, d, e] ;
L = [f, g, i, h] 

请注意，dfs_paths/2为您提供备用路径的回溯。如果您想预先列出所有这些，您可以尝试：

?- tree(T), findall(P, dfs_paths(T, P), Ps).
Ps = [[f, b, a], [f, b, d, c], [f, b, d, e], [f, g, i, h]].

如果您想要上面写的术语的平面列表，您可以flatten/2得到结果。