prolog - Prolog中的树后序遍历

Question

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

返回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,[]).

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

score 5 · Accepted Answer

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

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

用法：

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

您只需决定将 [X] 放在序列中的哪个位置即可获得不同的顺序。

score 0 · Accepted Answer

在后序的情况下，您必须遍历左分支并获取节点值列表Left，然后遍历右分支并获取节点值列表Right，最后返回 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, []).

但是请注意，从它不是尾递归的意义上说，此代码是次优的。您应该考虑在累加器的帮助下实现它。

2 回答 2