Prolog中的树后序遍历 [英] Tree postorder traversal in Prolog

问题描述

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

Tree traversal refers to the process of visiting each node in a tree data structure in a systematic way. The postorder traversal in the following image

Sorted_binary_tree

返回A、C、E、D、B、H、I、G、F(左、右、根).PREORDER 遍历的 Prolog 代码是

returns A, C, E, D, B, H, I, G, F (left, right, root). The Prolog code for PREORDER traversal is

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

preorder(void,[]).

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

I would like to modify the above code to implement postorder traversal.

推荐答案

如果是后序，则必须遍历左分支并获取节点值列表 Left，然后遍历右分支并得到一个节点值列表Right，最后返回Left、Right和节点值的串联.

In case of a postorder you have to traverse the left branch and get a list of node values Left, then traverse the right branch and get a list of node values Right, and finally return the concatenation of Left, Right and the node value.

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

Therefore, to modify your code would be to rearrange the way in which you instantiate the resulting list:

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

但是请注意，这段代码不是尾递归的，这是次优的.您应该考虑借助累加器来实现它.

Note however, that this code is suboptimal in the sense that it is not tail recursive. You should consider implementing it with the aid of an accumulator.

这篇关于Prolog中的树后序遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！