PROLOG (Как оформить заказ многолинейного дерева)

Question

Я борюсь с домашним заданием Пролога, как показано ниже,

Пролог использует общие деревья, а не двоичные деревья. Примером является

     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

Любая помощь этой головоломки приветствуется.

Answer 1

Я даю вам решение, которое работает для более чистого представления данных, которое работает исключительно путем сопоставления с образцом и не требует каких-либо 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 работать с вашим представлением деревьев (что я не рекомендую, поскольку вы не можете описывать решения только с помощью сопоставления с образцом, хотя это вполне возможно при другом представлении, как я покажу выше).

Answer 2

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([]).

Answer 3

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 - обход дерева в прологе

Код имеет предзаказ, порядок, порядок и порядок уровней.

Посмотрите на них все, вы можете найти их полезными.

Выход:

?- 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. Снова и снова и снова.