В порядке обхода дерева в Прологе - PullRequest
Новая
       12

В порядке обхода дерева в Прологе

2 голосов
/ 01 февраля 2012

Я новичок в Прологе и пытаюсь написать обход дерева по порядку, где приведен список фактов, таких как: 

leftSubtree(9, 7).
leftSubtree(7, 1).
leftSubtree(1, -2).
leftSubtree(11, 9).
leftSubtree(16, 13).
leftSubtree(3, 2).
rightSubtree(9, 11).
rightSubtree(7, 6).
rightSubtree(1, 3).
rightSubtree(11, 16).
rightSubtree(16, 19).

Я могу использовать inOrder (9, X).распечатать дерево по порядку.Я попытался использовать следующий код, который работает, но надеялся на что-то более простое.Любые советы или помощь будут оценены. 

inOrder(Root, X):-
   \+ leftSubtree(Root,Left),
   \+ rightSubtree(Root,Left) ->
   X = [Root];
   leftSubtree(Root,Left), 
   rightSubtree(Root,Right)->
   inOrder(Left, LeftNode),
   inOrder(Right, RightNode),
   append(LeftNode,[Root|RightNode],X);
   leftSubtree(Root,Left), 
   inOrder(Left, LeftNode),
   append(LeftNode,[Root],X);
   rightSubtree(Root,Right)->
   inOrder(Right, RightNode),
   append([Root],RightNode,X).

Ответы [ 3 ]

2 голосов
/ 01 февраля 2012

Ваш код можно упростить, избегая отрицательных тестов и используя некоторые рефлексивность Пролога. 

inOrder(Root, [Left, Root, Right]) :-
  inOrder(leftSubtree, Root, Left),
  inOrder(rightSubtree, Root, Right).

inOrder(BranchToExplore, Root, Subtree) :-
   call(BranchToExplore, Root, Branch)
   ->  inOrder(Branch, Subtree)
   ;   Subtree = [].

Это восстанавливает структуру дерева, как вложенный троичный список, затем достаточно одного вызова flatten / 2, чтобы, ну, flat , как в вашем оригинале требование. 

?- inOrder(8, Tree), flatten(Tree, L).
Tree = [[[[[], -2, []], 1, [[[], 2, []], 3, []]], 5, [[], 6, []]], 8, [[[], 9, [[], 10|...]], 11, [[[], 13|...], 16, [...|...]]]],
L = [-2, 1, 2, 3, 5, 6, 8, 9, 10|...].

Если у вашего Пролога нет call / N, вы можете использовать univ для создания вызываемого термина: 

inOrder(BranchToExplore, Root, Subtree) :-
  ( Callable =.. [BranchToExplore, Root, Branch], call(Callable) )
  ->  inOrder(Branch, Subtree)
  ;   Subtree = [].

Если мы поменяем местами Left и Root, у нас будет более полезное представление preOrder: preOrder(Root, [Root, Left, Right]) :- ....

Наличие структуры дерева в preOrder может быть полезно для дальнейшего процесса: одна «готовая к работе» и полезная реализация в SWI-Prolog - это XML, где деревья представлены как элемент (Tag, Attributes, Subtrees) и могут быть обработано библиотекой (xpath) . Может быть полезным изменить как inOrder / 2, так и inOrder / 3 для восстановления XML.

2 голосов
/ 01 февраля 2012

Попробуйте: 

inOrder(N,X) :- traverseLeft(N,L), traverseRight(N,R), append(L,[N|R],X).
traverseLeft(N,L) :- leftSubtree(N,M) -> inOrder(M,L); L=[].
traverseRight(N,R) :- rightSubtree(N,M) -> inOrder(M,R); R=[].

Есть еще немного возможностей для улучшения.append / 3 довольно дорог, но вы можете избежать этого, используя аккумуляторы.

Идея аккумулятора состоит в том, что вместо написания предиката inOrder(N,X), что означает «обход по порядку дерева с корнем вN - это X », вы пишете inOrder(N,A,X), что означает« обход по порядку дерева, корня которого в N, добавленного к A, есть X ».Затем вы просто запускаете его, вызывая inOrder(Root,[],X).

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

inOrder(N,X) :- inOrder_aux(N,[],X).
inOrder_aux(N,A,X) :- traverseLeft(N,[N|R],X), traverseRight(N,A,R).
traverseLeft(N,A,L) :- leftSubtree(N,M) -> inOrder_aux(M,A,L); L=A.
traverseRight(N,A,R) :- rightSubtree(N,M) -> inOrder_aux(M,A,R); R=A.

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

0 голосов
/ 07 февраля 2012

Деревья лучше представлены в Прологе логическими терминами.Подробное обсуждение, включая ответ на вашу проблему, можно найти здесь (см. Решения)

https://sites.google.com/site/prologsite/prolog-problems/4

...