序言中的树序遍历

问题描述：

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

返回F，B，A，d，C，E，G，I，H（根，左，右）。这是Prolog的代码：

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

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

答

尝试了这一点尺寸为

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 backt机架给你的替代路径。如果你希望他们所有的列表前面，你可以尝试：

?- 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结果。

非常好！如果你删除了剪辑，你可以在所有方向上使用它。当你描述一个列表时，考虑使用DCG符号，它可能更方便，尽管在这种情况下不是很多。 – mat 2012-04-11 08:27:30

答

添加一个参数PathToRoot你在哪里缺点当前节点，在将它传递给左/右访问者之前。

在返回之前，叶子谓词将统一收到的累加器及其反向值。

根呼叫将有一个空的累加器。与代表树实际上是从here

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).

测试出来：

序言中的树序遍历

相关推荐