Prolog中的树后序遍历

Question

树遍历是指以系统化的方式访问树形数据结构中的每个节点的过程。下图中的后序遍历：

Sorted_binary_tree

返回A, C, E, D, B, H, I, G, F (左，右，根)。 PREORDER遍历的Prolog代码如下：

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

preorder(void,[]).

我希望您能修改上述代码以实现后序遍历。

- Mark

Answer 1

各位，请在描述列表时考虑使用DCGs，例如：

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

使用方法：

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

你只需决定在序列中放置 [X] 的位置，便可以得到不同的顺序。

- mat

Answer 2

如果是后序遍历，您需要遍历左分支并获取节点值列表Left，然后遍历右分支并获取节点值列表Right，最后返回Left、Right和节点值的连接。

因此，要修改您的代码，需要重新排列实例化结果列表的方式：

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

请注意，这段代码并不是尾递归的，因此它的效率不够高。建议您使用累加器来实现它。

- gusbro