Взяв дерево и составив список

Question

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

build_tree([X,Y],'Tree'(X,Y)) :- !.

build_tree([X|Y],'Tree'(X,Z)) :- build_tree(Y, Z).

Если я захочу изменить процесс, взять дерево и изменить его обратно в список, как бы я это сделал?

Answer 1

flatten(leaf, []).
flatten(node(L, E, R), Ls) :-
    flatten(L, Ls1),
    append(Ls1, [E], Ls2),
    flatten(R, Ls3),
    append(Ls2, Ls3, Ls). 

, если вы рассматриваете узел дерева задницы (лист, элемент, лист), например,

flatten(node(node(leaf,2,leaf),3,node(leaf,5,leaf)),X).

дает X=[2,3,5].

и если вы хотите иметь bst

Список в дерево.

insert(E,leaf,node(leaf,E,leaf)).
insert(E,node(L,N,R),T) :-
 E >= N,
 T=node(L,N,R1),
 insert(E,R,R1).
insert(E,node(L,N,R),T) :-
 E < N,
 T=node(L1,N,R),
 insert(E,L,L1).

list_to_tree(List,Tree) :-
    list_to_tree(List,leaf,Trea2),
    Tree=Trea2.
list_to_tree([],Tree,Tree).
list_to_tree([H|T],Tree,St):-
 insert(H,Tree,R),
 list_to_tree(T,R,St).

Answer 2

Просто любопытно, как эта детерминированная версия сыграет?Предполагая, что был только один возможный список из дерева, например:

('Tree'('Tree'(nil, 2, nil), 5, 'Tree'(nil, 6, nil)).

, который дает: L = [5, 2, 6]

Answer 3

Если вы удалите вырез из первого правила, ваш код готов к работе в «обратном» режиме:

?- build_tree([1,2,3,4],T).
T = 'Tree'(1, 'Tree'(2, 'Tree'(3, 4))) ;
false.

?- build_tree(X,$T).
X = [1, 'Tree'(2, 'Tree'(3, 4))] ;
X = [1, 2, 'Tree'(3, 4)] ;
X = [1, 2, 3, 4] ;
false.

Answer 4

Обратите внимание, что преобразование вашего дерева-> списка не является функцией, поскольку деревья могут соответствовать нескольким спискам:

?- build_tree([1, 2, 3], T).
T = 'Tree'(1, 'Tree'(2, 3)).

?- build_tree([1, 'Tree'(2, 3)], T).
T = 'Tree'(1, 'Tree'(2, 3)).

Если вы хотите предикат, который может генерировать все списки из дерева, удалите вырез из build_tree и примените его с переменным первым аргументом. Если вы хотите детерминированное преобразование, напишите новый предикат tree_to_list.