Ширина в двоичном дереве - с использованием полуконтекстной записи

Я хотел бы вычислить список, являющийся порядком BFS на двоичном дереве. Более того, он должен работать во второй стороне - для списка он находит дерево.
Можете ли вы дать мне подсказку, пока я использовал что-то подобное, конечно, это не работает...

bfs(nil) --> [].
bfs(t(X, L, R)), [X] --> bfs(L), bfs(R).
Источник

2 ответа

Решение

Похоже, @repeat предложил отличное решение DCG. Тем временем я придумал "традиционное" решение на основе очередей, не являющееся DCG:

bfs_tree_list(nil, []).
bfs_tree_list(Tree, List) :-
    bfs_q_list([Tree], List).

bfs_q_list([], []).
bfs_q_list([t(X,L,R)|Qs], [X|Xs]) :-
    enqueue(L, Qs, Q1),
    enqueue(R, Q1, Q2),
    bfs_q_list(Q2, Xs).

% "naive" enqueue using append
enqueue(nil, Q, Q).
enqueue(t(X,L,R), Q1, Q2) :- append(Q1, [t(X,L,R)], Q2).

Это следует методике, показанной в ссылках, которые я предоставил в моих комментариях. Он также следует строгому порядку обхода слева направо, который, как я полагаю, является обычным в обходах двоичного дерева. Это немного проще, чем в ссылках, так как они предназначены для более общих графов, а не для бинарных деревьев. Описание того, что происходит выше, просто:

  1. Начните с верхнего уровня в очереди
  2. Для каждого элемента в очереди (пока очередь не пуста)
      (а) Выведите из очереди и примите текущее значение узла
      (б) поставить в очередь левый и правый узлы

Приведенный выше код дает:

| ?- bfs_tree_list(t(3,t(1,nil,t(2,nil,nil)),t(4,nil,nil)), L).

L = [3,1,4,2]

(1 ms) yes

А также:

| ?- bfs_tree_list(Tree, [3,1,4,2]).

Tree = t(3,nil,t(1,nil,t(4,nil,t(2,nil,nil)))) ? a

Tree = t(3,nil,t(1,nil,t(4,t(2,nil,nil),nil)))

Tree = t(3,nil,t(1,t(4,nil,t(2,nil,nil)),nil))

Tree = t(3,nil,t(1,t(4,t(2,nil,nil),nil),nil))

Tree = t(3,nil,t(1,t(4,nil,nil),t(2,nil,nil)))

Tree = t(3,t(1,nil,t(4,nil,t(2,nil,nil))),nil)

Tree = t(3,t(1,nil,t(4,t(2,nil,nil),nil)),nil)

Tree = t(3,t(1,t(4,nil,t(2,nil,nil)),nil),nil)

Tree = t(3,t(1,t(4,t(2,nil,nil),nil),nil),nil)

Tree = t(3,t(1,t(4,nil,nil),t(2,nil,nil)),nil)

Tree = t(3,t(1,nil,nil),t(4,nil,t(2,nil,nil)))

Tree = t(3,t(1,nil,nil),t(4,t(2,nil,nil),nil))

Tree = t(3,t(1,nil,t(2,nil,nil)),t(4,nil,nil))

Tree = t(3,t(1,t(2,nil,nil),nil),t(4,nil,nil))

(1 ms) no
| ?-

Вот пересмотренная версия, которая использует список различий, а не append/3,

bfs_tree_list(nil, []).
bfs_tree_list(Tree, List) :-
    bfs_q_list([Tree|T], T, List).

bfs_q_list(Q, T, []) :- Q == T, !.
bfs_q_list([t(X,L,R)|Qs], T, [X|Xs]) :-
    [t(X,L,R)|Qs] \== T,
    enqueue(L, T1, T),
    enqueue(R, NewT, T1),
    bfs_q_list(Qs, NewT, Xs).

enqueue(nil, Q, Q).
enqueue(t(X,L,R), T, [t(X,L,R)|T]).
Источник

Вот как вы можете сделать это, используя dcg (без полуконтекстов) и аккумуляторы:

tree_bfss(T, Xs) :-
   phrase(bfs1([T]), Xs).

bfs1([]) --> [].                    % done if level is empty           
bfs1([X|Xs]) -->
   step_(X, [], Ts),                % single step
   bfs0_(Xs, Ts).                   % process items in this level

bfs0_([], Ts) -->               
   bfs1(Ts).                        % process next level
bfs0_([X|Xs], Ts0) -->
   step_(X, Ts0, Ts),               % single step
   bfs0_(Xs, Ts).                   % continue with this level

step_(nil, Ts, Ts) --> [].
step_(t(L,M,R), Ts, [R,L|Ts]) -->   % push R and L to the next level
   [M].                             % take care of M right now

Пример запроса с использованием SICStus Prolog 4.3.2:

| ?- tree_bfss(t(t(nil,1,t(nil,2,nil)),3,t(nil,4,nil)), Xs).
Xs = [3,4,1,2] ? ;
no

Как насчет того, чтобы идти в "другом" направлении?

| ?- tree_bfss(T, [3,4,1,2]).
T = t(t(t(t(nil,2,nil),1,nil),4,nil),3,nil) ? ;
T = t(t(t(nil,1,t(nil,2,nil)),4,nil),3,nil) ? ;
T = t(t(nil,4,t(t(nil,2,nil),1,nil)),3,nil) ? ;
T = t(t(nil,4,t(nil,1,t(nil,2,nil))),3,nil) ? ;
T = t(t(t(nil,2,nil),4,t(nil,1,nil)),3,nil) ? ;
T = t(nil,3,t(t(t(nil,2,nil),1,nil),4,nil)) ? ;
T = t(nil,3,t(t(nil,1,t(nil,2,nil)),4,nil)) ? ;
T = t(nil,3,t(nil,4,t(t(nil,2,nil),1,nil))) ? ;
T = t(nil,3,t(nil,4,t(nil,1,t(nil,2,nil)))) ? ;
T = t(nil,3,t(t(nil,2,nil),4,t(nil,1,nil))) ? ;
T = t(t(nil,1,nil),3,t(t(nil,2,nil),4,nil)) ? ;
T = t(t(nil,1,nil),3,t(nil,4,t(nil,2,nil))) ? ;
T = t(t(t(nil,2,nil),1,nil),3,t(nil,4,nil)) ? ;
T = t(t(nil,1,t(nil,2,nil)),3,t(nil,4,nil)) ? ;
no

редактировать

Полезные комментарии предложили уточнить порядок пунктов списка:

  • Приведенный выше код не гарантирует какой-либо конкретный порядок на каждом уровне дерева.

  • Это гарантирует, что все элементы i- го уровня находятся перед всеми элементами (i+1) -го уровня.

(Это сделало реализацию немного проще.)

Источник
Другие вопросы по тегам