Prolog - Конкатенация на списък в дървета

Трябва да напиша предикат 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
    • полезния товар на текущия възел
    • сплесканото дясно поддърво

Кодът на Prolog за постигане на това е почти идентичен с описанието на английски по-горе:

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