ПРОЛОГ (Как postorder в многоходовую дерево)

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

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 Traversal in Prolog

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

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

Выход:

?- 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 . 

Edit: В конце tree запроса я добавил ! так что остановит откаты на первом true.. В противном случае после true., если вы набрали ;, вы получите true. снова и снова.

Answer 2

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

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