4

我想计算列表是二叉树上的 bfs 顺序。此外，它应该在第二面工作 - 列出它找到树。
你能给我一些提示吗，到目前为止我都使用过类似的东西，当然它不起作用......

bfs(nil) --> [].
bfs(t(X, L, R)), [X] --> bfs(L), bfs(R).
4

2 回答 2

4

这就是使用（没有半上下文）和累加器的方法：

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)层的所有项目之前。

（这使实现稍微简单了一些。）

于 2016-05-24T10:20:30.927 回答
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. 对于队列中的每个元素（直到队列为空）
      (a) 出队并接受当前节点值
      (b) 将左右节点入队

上面的代码产生：

| ?- 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]).
于 2016-05-24T13:11:44.647 回答