Пролог — объединение списков в деревьях

Мне нужно написать предикат ListInTree(T,X), который верен, когда T — это дерево со списком в каждом узле, а X — это объединение всех списков (при условии посещения в предварительном порядке).

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

Спасибо


prolog dcg
person Andrea Ottaviani    schedule 06.05.2015    source источник
comment
Можете ли вы показать несколько (7) примеров?   -  person User    schedule 06.05.2015
comment
Как представлено дерево в задаче, которую вам предстоит решить? Попытайтесь увидеть, какие термины используются для его представления, и используйте предложения для работы с каждым из них, используя рекурсию, когда любой из этих терминов имеет поддеревья.   -  person migfilg    schedule 06.05.2015

Ответы (2)


arrow_upward
2
arrow_downward

Вы не указываете, какое дерево вам нужно, так что я должен догадаться. Лучше всего в этом случае использовать DCG, поскольку грамматики созданы для моделирования конкатенации наиболее естественным образом:

seq([]) -->
   [].
seq([E|Es]) -->
   [E],
   seq(Es).

flattened(empty) -->
   [].
flattened(node(Xs, L, R)) -->
   seq(Xs),
   flattened(L),
   flattened(R).

tree_flattened(T, Es) :-
   phrase(flattened(T), Es).
person false    schedule 07.05.2015

arrow_upward
1
arrow_downward

Для примера примем следующее представление дерева:

  • Атом nil представляет собой пустое дерево.
  • Структура tree/3 представляет собой непустое дерево tree( Left , Right , Payload ), где Left и Right представляют (соответственно и рекурсивно) левое и правое поддеревья, а Payload — это полезная нагрузка для узла: в вашем случае список.

Многие/наиболее рекурсивные проблемы имеют 1 или 2 «особых случая» и более общий случай. Это ничем не отличается:

Особым случаем является пустое дерево: его сведение дает пустой список.

Общий случай — это непустое дерево: его сглаживание состоит из следующих шагов:

  • Сгладьте левое поддерево, чтобы создать список
  • Сгладить правое поддерево, чтобы создать список

  • Результат получается конкатенацией

    • the flattened left subtree
    • полезная нагрузка текущего узла
    • сплющенное правое поддерево

Код Пролога для этого почти идентичен вышеприведенному английскому описанию:

flatten_tree( nil                      , []     ) .  % flattening the empty tree yields an empty list, n'est-ce-pas?
flatten_tree( tree(Left,Right,Payload) , Result ) :- % flattening a non-empty tree consists of
   flatten_tree( Left  , Prefix ) ,                  % - flattening the left subtree,
   flatten_tree( Right , Suffix ) ,                  % - flattening the right subtree,
   concatenate( Prefix , Payload , Suffix , Result ) % - concatenating the three parts
   .                                                 % - easy!

concat( Xs, Ys , Zs , Rs ) :-
  append(Xs,Ys,T1) ,
  append(T1,Zs,Rs)
  .

Можно заметить, что другим подходом может быть использование findall/3 и append/2. (если вы используете пролог SWI).

Сначала вам нужен предикат для посещения дерева с возвратом:

visit( tree(L,_,_) , P ) :- visit( L , P ) . % visit the left subtree
visit( tree(_,_,P) , P ) .                   % visit the current node
visit( tree(_,R,_) , P ) :- visit( R , P ) . % visit the right subtree

Не стесняйтесь изменять порядок предложений, чтобы получить желаемый порядок. Как только вы это сделаете, сведение дерева будет тривиальным:

flatten_tree( Tree , List ) :-
  findall( X, visit(Tree,X) , Xs ) ,
  append(Xs,List)
  .
person Nicholas Carey    schedule 07.05.2015