Převést seznam adjacencies na rekurzivní formátu

Question 1

Dán binární strom, ve formátu seznamu adjacencies jako [1-8,1-2,...] Prvky v seznamu jsou v žádném konkrétním pořadí. Vzhledem kořen stromu seznamu musí být převedeny na rekurzivní formátu t(L,Root,R). Kde L a R jsou stromy samotné, nebo nulová.

To je to, co jsem se snažil:

 % convert binary tree from adjacencies list to recursive term format.
 % make_tree(AdjList, Root, Tree)

 make_tree([],Root,t(nil,Root,nil)):-!.
 make_tree([Root-X],Root,t(X,Root,nil)).
 make_tree([Root-X],Root,t(nil,Root,X)):-!.
 make_tree(_,nil,nil):-!.


 make_tree(N,Root,t(L,Root,R)):-
    find_kids(N,Root,C,S),
    reorder(C,[C1,C2]),
    make_tree(S,C1,L), make_tree(S,C2,R).

% reorder 2 out of 2
reorder([X,Y],[Y,X]).
reorder([X,Y],[X,Y]).

% find children and remove them from list of nodes
find_kids(L,Root,[C1,C2],R):-
   find_children(L,Root,[C1,C2|_],R).

find_children([Root-Y|Xs],Root,[Y|T],Acc):-
   find_children(Xs,Root,T,Acc).

find_children([X-Y|Xs],Root,R,[X-Y|Acc]):-
   X \= Root,
   find_children(Xs,Root,R,Acc).

find_children([],_,[nil,nil],[]).

Question 2

Zvažte následující binární strom a libovolný seznam sousedů pro to:

%        0
%      /   \
%     1     2
%    / \   / \
%   3   4 5   6
%  / \     \
% 7   8     9

adj_list([1-3,0-2,1-4,5-9,3-7,2-5,2-6,3-8,0-1]).

Aby si děti uzlu, můžete použít následující predikát:

find_children(Root, List, Children, Rest) :-
    partition({Root}/[X-_]>>(X=Root), List, Children0, Rest),
    maplist([Root-Child, Child]>>true, Children0, Children).

Příklady:

?- adj_list(List), find_children(3, List, Children, Rest).
List = [1-3, 0-2, 1-4, 5-9, 3-7, 2-5, 2-6, 3-8, ... - ...],
Children = [7, 8],
Rest = [1-3, 0-2, 1-4, 5-9, 2-5, 2-6, 0-1].

?- adj_list(List), find_children(5, List, Children, Rest).
List = [1-3, 0-2, 1-4, 5-9, 3-7, 2-5, 2-6, 3-8, ... - ...],
Children = [9],
Rest = [1-3, 0-2, 1-4, 3-7, 2-5, 2-6, 3-8, 0-1].

?- adj_list(List), find_children(4, List, Children, Rest).
List = Rest, Rest = [1-3, 0-2, 1-4, 5-9, 3-7, 2-5, 2-6, 3-8, ... - ...],
Children = [].

Stavět všechny možné binární stromy z dané root, můžete použít následující kód:

% trees(+Root, -Tree)

trees(Root, Tree) :-
    adj_list(List),
    make_tree(Root, List, _Rest, Tree).

% make_tree(+Root, +List, -Rest, -Tree)

make_tree(Root, List, Rest, Tree) :-
    find_children(Root, List, Children, Rest0),
    make_tree(Children, Root, Rest0, Rest, Tree).

make_tree([], Root, List, List, t(nil, Root, nil)).

make_tree([X], Root, List, Rest, Tree) :-
    make_tree(X, List, Rest, Subtree),
    (   Tree = t(Subtree, Root, nil)
    ;   Tree = t(nil, Root, Subtree) ).

make_tree([X,Y], Root, List, Rest, Tree) :-
     make_tree(X, List, Rest0, Subtree1),
     make_tree(Y, Rest0, Rest, Subtree2),
     (   Tree = t(Subtree1, Root, Subtree2)
     ;   Tree = t(Subtree2, Root, Subtree1) ).

Příklady:

?- trees(4, T).
T = t(nil, 4, nil).

?- trees(3, T).
T = t(t(nil, 7, nil), 3, t(nil, 8, nil)) ;
T = t(t(nil, 8, nil), 3, t(nil, 7, nil)).

?- trees(5, T).
T = t(t(nil, 9, nil), 5, nil) ;
T = t(nil, 5, t(nil, 9, nil)) ;
false.

?- trees(2, T).
T = t(t(t(nil, 9, nil), 5, nil), 2, t(nil, 6, nil)) ;
T = t(t(nil, 6, nil), 2, t(t(nil, 9, nil), 5, nil)) ;
T = t(t(nil, 5, t(nil, 9, nil)), 2, t(nil, 6, nil)) ;
T = t(t(nil, 6, nil), 2, t(nil, 5, t(nil, 9, nil))) ;
false.

slago · Answer 1 · 2021-11-23T18:00:34

Zvažte následující binární strom a libovolný seznam sousedů pro to:

%        0
%      /   \
%     1     2
%    / \   / \
%   3   4 5   6
%  / \     \
% 7   8     9

adj_list([1-3,0-2,1-4,5-9,3-7,2-5,2-6,3-8,0-1]).

Aby si děti uzlu, můžete použít následující predikát:

find_children(Root, List, Children, Rest) :-
    partition({Root}/[X-_]>>(X=Root), List, Children0, Rest),
    maplist([Root-Child, Child]>>true, Children0, Children).

Příklady:

?- adj_list(List), find_children(3, List, Children, Rest).
List = [1-3, 0-2, 1-4, 5-9, 3-7, 2-5, 2-6, 3-8, ... - ...],
Children = [7, 8],
Rest = [1-3, 0-2, 1-4, 5-9, 2-5, 2-6, 0-1].

?- adj_list(List), find_children(5, List, Children, Rest).
List = [1-3, 0-2, 1-4, 5-9, 3-7, 2-5, 2-6, 3-8, ... - ...],
Children = [9],
Rest = [1-3, 0-2, 1-4, 3-7, 2-5, 2-6, 3-8, 0-1].

?- adj_list(List), find_children(4, List, Children, Rest).
List = Rest, Rest = [1-3, 0-2, 1-4, 5-9, 3-7, 2-5, 2-6, 3-8, ... - ...],
Children = [].

Stavět všechny možné binární stromy z dané root, můžete použít následující kód:

% trees(+Root, -Tree)

trees(Root, Tree) :-
    adj_list(List),
    make_tree(Root, List, _Rest, Tree).

% make_tree(+Root, +List, -Rest, -Tree)

make_tree(Root, List, Rest, Tree) :-
    find_children(Root, List, Children, Rest0),
    make_tree(Children, Root, Rest0, Rest, Tree).

make_tree([], Root, List, List, t(nil, Root, nil)).

make_tree([X], Root, List, Rest, Tree) :-
    make_tree(X, List, Rest, Subtree),
    (   Tree = t(Subtree, Root, nil)
    ;   Tree = t(nil, Root, Subtree) ).

make_tree([X,Y], Root, List, Rest, Tree) :-
     make_tree(X, List, Rest0, Subtree1),
     make_tree(Y, Rest0, Rest, Subtree2),
     (   Tree = t(Subtree1, Root, Subtree2)
     ;   Tree = t(Subtree2, Root, Subtree1) ).

Příklady:

?- trees(4, T).
T = t(nil, 4, nil).

?- trees(3, T).
T = t(t(nil, 7, nil), 3, t(nil, 8, nil)) ;
T = t(t(nil, 8, nil), 3, t(nil, 7, nil)).

?- trees(5, T).
T = t(t(nil, 9, nil), 5, nil) ;
T = t(nil, 5, t(nil, 9, nil)) ;
false.

?- trees(2, T).
T = t(t(t(nil, 9, nil), 5, nil), 2, t(nil, 6, nil)) ;
T = t(t(nil, 6, nil), 2, t(t(nil, 9, nil), 5, nil)) ;
T = t(t(nil, 5, t(nil, 9, nil)), 2, t(nil, 6, nil)) ;
T = t(t(nil, 6, nil), 2, t(nil, 5, t(nil, 9, nil))) ;
false.

Převést seznam adjacencies na rekurzivní formátu

Otázka

Nejlepší odpověď

V jiných jazycích

Tato stránka je v jiných jazycích

Populární v této kategorii

Oblíbené položky v této kategorii