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

Question

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

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

Благодаря

Answer 1

Ради примера, давайте предположим следующее представление для дерева:

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

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

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

Общий случай сводится к роли непустое дерево: прокатка состоит из следующих этапов:

• Свести левое поддерево для получения списка
• Свести правое поддерево на продукт список

• результат, который получается путем конкатенации

  • уплощенной левой поддерево
  • полезной нагрузки текущего узла
  • уплощенный правое поддерево

Код 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) 
    . 

Answer 2

Вы не указываете, какое дерево вы после, так что я должен угадать.Лучшим в этом случае является использование 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).