Дерево в список (обновлено) - PullRequest
Новая
       27

Дерево в список (обновлено)

3 голосов
/ 28 марта 2012

Я попробовал предложение из чьего-то комментария в другом посте о том, как превратить дерево в список. Однако у меня где-то есть (или что-то еще) необъявленные переменные, поэтому мои значения в моем списке [_G667, _G673, _G679] вместо [5, 2, 6], что является правильным ответом. Насколько мне известно, все манипуляции верны.

Вот код: 

flatten( Item , []).

flatten( tree(Left, Val, Right), List) :-
  flatten(Left, List1),
  append(List1, [E], List2),
  flatten(Right, List3),
  append(List2, List3, List).

Я использовал следующий запрос: 

?- flatten(tree(tree(nil, 2, nil), 5, tree(nil, 6, nil)), L).

Кто-нибудь видит проблему с переменной? Я думал, что это может быть в первой строке (с Item), но если я изменяю Item на item, запрос немедленно возвращает false.

Я написал только несколько программ на Прологе, так что для меня это все еще новая концепция.

Ответы [ 3 ]

2 голосов
/ 28 марта 2012

Есть несколько вопросов. Давайте начнем с самого фундаментального: у вас есть дерево следующего типа. 

is_tree(nil).
is_tree(tree(L,_E,R)) :-
   is_tree(L),
   is_tree(R).

Ваша программа должна отражать этот тип. Я сказал «тип»? Ну, is_tree/1 - это предикат, как и любой другой.

Другая проблема заключается в интенсивном использовании append/3. Недаром многие системы Prolog не предлагают append/3, потому что часто предпочтительнее составлять конкатенацию с помощью s. 

tree_elements(nil) --> [].
tree_elements(tree(L,E,R)) -->
   tree_elements(L),
   [E],
   tree_elements(R).

Теперь вы можете использовать это 

?- <b>phrase(tree_elements(tree(tree(nil, 2, nil), 5, tree(nil, 6, nil))), Es).</b>
Es = [2,5,6].
2 голосов
/ 28 марта 2012

Я считаю, E следует изменить на Val. Val не используется (!) И E происходит из ниоткуда.

Кроме того, чтобы это работало, вы должны изменить Item на nil.

1 голос
/ 28 марта 2012

Что @aioobe сказал. Я думаю, что вы также используете append/3 больше, чем следовало бы. Предполагая, что ваше древовидное представление выглядит так: 

tree( Left_subtree, Data , Right_subtree )

с атомом nil, представляющим пустое дерево, я полагаю, что вы могли бы достичь того же эффекта таким образом: 

flatten( nil , [] ).
flatten( tree( Left , Data , Right ) , Flat ) :-
  flatten( Left  , Pfx ) ,
  flatten( Right , Sfx ) ,
  append( Pfx , [Data|Sfx] , Flat  )
  .
...