Prolog二叉树搜索

Question

我遇到了这个问题：

编写一个PROLOG程序，该程序给定一个二叉树，其中整数存储在节点中。写一个 返回树中存储的最大值的程序。例如，给定输入[4,[1,[],[]],[7,[],[]]]算法应返回7。

我想我必须使用BFS。这是我关于BFS的讲义：

bf(X,Y), Y是包含树 X 元素的列表，如在广度优先访问中遇到的。

bf([], []).
bf([void | Rest], Y):- bf(Rest, Y).
bf([tree(Integer, Right, Left) | Rest], [Integer | Y]) :- 
append(Rest, [Left, Right], Nodes), 
bf(Nodes, Y).

我什至不知道所有变量意味着什么...希望得到一些帮助。

Answer 1

好的，你展示的bf/2谓词很好，除了描述应该是

bf([X], Y)：Y是包含树X元素的列表，如树遍历的广度第一阶所遇到的。

这里又有一些更长的描述性变量名称(我通常更喜欢非常短，甚至只有一个字母的名称，如果需要，可以在注释中描述; 稍后，当您对Prolog更熟悉时，您可能也会这样做(，并且一些隐含的统一变成了明确的统一：

bf(Queue, Integers) :- 
Queue    = [],                     %% breadth-first enumeration of the empty queue
Integers = [].                     %% is the empty list
bf([HeadOfQueue | RestOfQueue], Integers):- 
HeadOfQueue = void,                %% empty tree in the queue,
bf(RestOfQueue, Integers).         %% go on with the same Integers list to fill
bf([HeadOfQueue | RestOfQueue], Integers) :- 
HeadOfQueue = tree(Integer, Right, Left),            %% a tree in the queue,
Integers = [Integer | MoreIntegers],                 %% fill the list's head
append(RestOfQueue, [Left, Right], ExtendedQueue),   %% extend the popped queue
%%   with Left, then Right,
bf(ExtendedQueue, MoreIntegers).                     %% and keep going

它从"议程"队列中弹出一个节点，取出节点的整数，将其放入以自上而下的方式构建的结果列表中，将节点的两个子节点附加到议程的后部，然后递归。因此，这应该以[Tree]作为初始队列进行调用。因此，按 FIFO 顺序考虑树，实现树的广度优先枚举。后进先出会让我们首先获得深度。

唯一剩下的就是，它适合在什么样的树上工作？答案就在代码中：它是形式的复合项

tree( Int, RightChild, LeftChild )

显然RightChild和LeftChild应该是相同形式的树/复合术语，或者......你看到了吗？...原子void.很可能是空树。

您在示例中显示的树具有另一种结构，大概是[Int, LeftChild, RightChild]结构。只需调整bf/2谓词以适应新的预期数据格式。

我们可以通过首先概括定义，抽象数据细节来做到这一点，使用

bf([], []).                       %% implicit unifications, shorter names
bf([Empty | Rest], Y):- 
empty(Empty),                                  %% data abstraction!
bf(Rest, Y).
bf([Node | RestOfQueue], [Integer | Y]) :- 
node(Node, Integer, Left, Right),              %% data abstraction!
append(RestOfQueue, [Left, Right], ExtendedQueue), 
bf(ExtendedQueue, Y).
empty( void ).
node( tree(Integer, Right, Left), Integer, Left, Right ).

现在剩下要做的就是重新定义empty/1和node/4以匹配您的树编码类型。这应该很简单。它就在示例数据中：

[4,
[1, [], []],
[7, [], []]  ]

所以

empty( ... ).
node( [ ..., ...., ... ] , ..., ..., ... ).

这样做后，我们将定义

maximum_element(Tree, MaxElem ):-
bf( [Tree],  TreeElements ),
list_maximum( TreeElements, MaxElem ).

起初，但后来我们可以将两个子目标融合为一个，这样最大整数的选取都是在树遍历本身期间完成的，而不是先构建它们的整个列表。