在Prolog的树后序遍历(Tree postorder traversal in Prolog)

树遍历指参观树数据结构中的每个节点用系统的方法的过程。 在postorder如下图的遍历

Sorted_binary_tree

返回A, C, E, D, B, H, I, G, F (left, right, root) 。 为序言码PREORDER遍历

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

preorder(void,[]).

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

Answer 1:

在后序的情况下，你必须遍历左支和获取节点值的列表Left ，然后遍历右支，并得到节点值的列表Right ，最后返回左，右的串联和node value 。

因此，修改代码将重新排列你实例结果列表的方式：

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

但是请注意，此代码是在这个意义上最理想的，它不是尾递归。 你应该考虑与蓄能器的帮助下实现它。

Answer 2:

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

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

用法：

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

您只需决定在何处放置[X]序列中获得不同的订单。

文章来源: Tree postorder traversal in Prolog