将邻接列表转换为递归格式

Question

给定一棵邻接列表格式的二叉树，例如 [1-8,1-2,...] 列表中的元素没有任何特定顺序。给定树的根，需要将列表转换为递归格式 t(L,Root,R)。其中 L 和 R 是树本身或 nil。

这是我试过的：

 % 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],[]).

Answer 1

考虑以下二叉树及其任意邻接表：

%        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]).

要获取节点的子节点，您可以使用以下谓词：

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

示例：

?- 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 = [].

要从给定根构建所有可能的二叉树，您可以使用以下代码：

% 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) ).

示例：

?- 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.

将邻接列表转换为递归格式

convert list of adjacencies to recursive format

binary-tree

prolog