Prolog二叉树搜索

Question

我遇到过这个问题：

Write a PROLOG program that given a binary tree of with integer numbers stored in the nodes. Write a program that returns the maximum value stored in the tree. For example, given the input [4,[1,[],[]],[7,[],[]]] the algorithm should return 7.

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

bf(X,Y), Y is the list containing the elements of the tree X, as encountered in the breadth-first visit.

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( <b>[X]</b>, Y): Y is the list containing the elements of a tree X, as encountered in the breadth-first order of tree traversal.

又来了，有一些更长的描述性变量名（我通常更喜欢非常短，甚至是一个字母的名称，如果需要，在评论中加上描述；你以后可能也会这样做，当你re more comfort with 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

从"agenda"队列中弹出一个节点，取出节点的整数，自顶向下放入正在构建的结果列表中，将节点的两个子节点追加到agenda的后面，并递归。因此，应该使用 [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 ).

一开始，但后来我们可以将两个子目标融合为一个，这样最大整数的选取就全部在树遍历过程中完成，而不是首先构建它们的整个列表。

Prolog二叉树搜索

Prolog binary tree search

tree

prolog

max

binary-tree

breadth-first-search