Обход Prolog Postorder в общем дереве с использованием univ

Я пытаюсь пройти общее дерево в прологе в обратном порядке. Я нашел много обходов двоичного дерева в обратном порядке, но не смог использовать их для своей цели. Я написал программу, но она печатает мое дерево только обратным способом, как вводится, т.е. для ввода 

?-postorder(a(b,c,d(e,f,g))).
->g f e d c b a true (is what I get)
->b c e f g d a true (what i want to get)

Вот код, который мне удалось написать до сих пор

postorder([]).
postorder(List):- List =..X , myfun(X).
myfun([A|B]):- atom(A), myfun(B),write(A),write(' ').
myfun([A|B]):- postorder(A),myfun(B).
myfun([]).

У меня нет способа обхода по порядку
Любая помощь очень ценится


tree prolog postorder
person Harsh Shah    schedule 20.11.2013    source источник
comment
возможный дубликат PROLOG (как разместить многоканальное дерево)   -  person Shevliaskovic    schedule 21.11.2013
comment
Ну, я видел этот вопрос, но там они не используют предикат univ в данных решениях. Я хотел сделать это с помощью univ.   -  person Harsh Shah    schedule 21.11.2013

Ответы (3)


arrow_upward
0
arrow_downward

ваше наименование аргументов немного сбивает с толку

postorder(List):- List =..X , myfun(X).

должен прочесть

postorder(Struct):- Struct =.. List, myfun(List).

Теперь должно быть яснее, что вы должны написать здесь структурный функтор:

postorder(Struct):-
  Struct =.. [Functor|Arguments], myfun(Arguments), write(Functor).

На этом этапе вы также должны изменить myfun...

В качестве примера приведем компактное решение задачи

postorder(X) :- X =.. [H|As], maplist(postorder, As), write(H).

что дает

?- postorder(a(b,c,d(e,f,g))).
bcefgda
person CapelliC    schedule 20.11.2013
comment
Я прошу прощения за мои соглашения об именах. Я новичок в прологе и не разбираюсь в этом. Итак, какую роль здесь играет maplist? - person Harsh Shah; 21.11.2013

arrow_upward
0
arrow_downward

Альтернативный способ сделать это -

Предложение - я бы структурировал ваше дерево немного по-другому, в частности, дерево в форме

tree(Value,[Subtrees])

где значение будет чем-то вроде a, а затем список представляет собой список поддеревьев. Лист имеет пустой список []

Если вы это сделаете, вы можете использовать этот алгоритм, используя унификацию.

postorder(tree(VAL,[Child1|ChildList])) :- postorder(Child1),postorder(tree(VAL,ChildList)).
postorder(tree(VAL,[])) :- write(VAL).

выход:

?- postorder(tree(a,[tree(b,[]),tree(c,[]),tree(d,[tree(e,[]),tree(f,[]),tree(g,[])])])).
bcefgda
true .
person C.B.    schedule 20.11.2013

arrow_upward
0
arrow_downward

Вот решение, которое отлично работает для меня.

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([]).
person Harsh Shah    schedule 22.11.2013