1

我正在为如下的 Prolog 作业而苦苦挣扎，

Prolog 使用通用树，而不是二叉树。一个例子是

     a(b,c,d(e,f,g))   where root a has 3 kids, as does kid d.

 It is possible to define both preorder and postorder for general trees, 
 although inorder of course makes no sense.

 For this assignment we are interested in postorder, which is defined as
 follows:

   to 'visit' a tree in postorder, 
      you visit the subtrees of the root, in left to right order,
      in postorder, and then you visit the root

 Thus the example above would yield the following postorder traversal:

        b c e f g d a

  Write Prolog code which will perform a postorder traversal of a Prolog
 tree constant.   Hint: you might use 'univ', or its cousins.

 Sample dialog:

 ?- postorder(a(b,c,d(e,f,g))).
 b c e f g d a    true

对此难题的任何帮助表示赞赏。

4

3 回答 3

3

我为您提供了一个适用于更清晰的数据表示的解决方案，该解决方案仅通过模式匹配工作，不需要任何univ等。我统一以tree(Node, Children). 您的示例可以用这种表示形式写成：

example(T) :-
        T = tree(a, [tree(b,[]),
                     tree(c,[]),
                     tree(d, [tree(e,[]),
                              tree(f,[]),
                              tree(g,[])])]).

现在，当您描述节点列表时，请考虑使用 DCG。例如：

postorder(tree(Node, Children)) -->
        postorder_(Children),
        [Node].

postorder_([]) --> [].
postorder_([C|Cs]) -->
        postorder(C),
        postorder_(Cs).

具有上述定义的示例查询及其结果：

?- example(T), phrase(postorder(T), Ns).
T = tree(a, ...),
Ns = [b, c, e, f, g, d, a].

我把它作为一个简单的练习，让这个 DCG 与你的树表示一起工作（我不建议这样做，因为你不能单独通过模式匹配来描述解决方案，尽管这显然可以用不同的表示来描述，如上所示）。

于 2013-11-17T21:49:09.903 回答
0 
postorder([]).
postorder(Tree):- Tree =..[Parent|Children] , myfun(Children), write(Parent),write(' ').
myfun([First|Next]):- atom(First), write(First), write(' '), myfun(Next).
myfun([First|Next]):- postorder(First),myfun(Next).
myfun([]).
于 2013-11-26T02:42:57.583 回答
0 
tree :-
Tree= [1,
        [2,
       [4,
         [7, nil, nil],
         nil], 
       [5, nil, nil]],
        [3,
     [6,
       [8, nil, nil], 
       [9,nil, nil]], 
     nil]],

write('preorder    : '), preorder(Tree), nl,
write('inorder     : '), inorder(Tree), nl,
write('postorder   : '), postorder(Tree), nl,
write('level-order : '), level_order([Tree]),!.

preorder(nil).
preorder([Node, FG, FD]) :-
format('~w ', [Node]),
preorder(FG),
preorder(FD).


inorder(nil).
inorder([Node, FG, FD]) :-
inorder(FG),
format('~w ', [Node]),
inorder(FD).

postorder(nil).
postorder([Node, FG, FD]) :-
postorder(FG),
postorder(FD),
format('~w ', [Node]).


level_order([]).

level_order(A) :-
level_order_(A, U-U, S),
level_order(S).

level_order_([], S-[],S).

level_order_([[Node, FG, FD] | T], CS, FS) :-
format('~w ', [Node]),
append_dl(CS, [FG, FD|U]-U, CS1),
level_order_(T, CS1, FS).

level_order_([nil | T], CS, FS) :-
level_order_(T, CS, FS).


append_dl(X-Y, Y-Z, X-Z).

通过 Rosetta Code - Prolog 中的树遍历

代码有preorder、inorder、postorder和level order。

看看它们，你可能会发现它们很有用。

输出：

?- tree.
 preorder    : 1 2 4 7 5 3 6 8 9 
 inorder     : 7 4 2 5 1 8 6 9 3 
 postorder   : 7 4 5 2 8 9 6 3 1 
 level-order : 1 2 3 4 5 6 7 8 9 
true .

编辑：在tree查询结束时我添加了，!所以它将停止回溯第一个true.. 否则之后true.，如果你输入;你会true.一次又一次地得到。

于 2013-11-17T20:28:02.287 回答