Prolog二叉树搜索
Prolog binary tree search
我遇到过这个问题:
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).
我什至不知道所有变量的含义...希望得到一些帮助。
好的,您显示的 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 ).
一开始,但后来我们可以将两个子目标融合为一个,这样最大整数的选取就全部在树遍历过程中完成,而不是首先构建它们的整个列表。
我遇到过这个问题:
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 return7
.
我想我必须使用 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).
我什至不知道所有变量的含义...希望得到一些帮助。
好的,您显示的 bf/2
谓词非常好,除了描述应该是
bf( <b>[X]</b>, Y)
:Y
is the list containing the elements of a treeX
, 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 ).
一开始,但后来我们可以将两个子目标融合为一个,这样最大整数的选取就全部在树遍历过程中完成,而不是首先构建它们的整个列表。