prolog - Prolog中的树后序遍历

Question

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

Sorted_binary_tree

返回 A, C, E, D, B, H, I, G, F (left, right, root) . PREORDER 的 Prolog 代码遍历是

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

preorder(void,[]).

我想修改上面的代码来实现后序遍历。

Answer 1

伙计们，请在描述列表时考虑使用 DCG，例如:

preorder(void) --> [].
preorder(tree(X, L, R)) -->
        [X],
        preorder(L),
        preorder(R).

用法:

?- phrase(preorder(Tree), List).

通过简单地决定在序列中放置 [X] 的位置，您可以获得不同的顺序。