时间戳

首页 > 解决方案 > Prolog：将树转换为顺序列表并检查列表是否已排序

arrays - Prolog：将树转换为顺序列表并检查列表是否已排序

问题描述

现在我想检查一棵树是否是搜索树，以便按顺序遍历是一个升序数组。（所以如果树被排序） - 它几乎可以工作。但是我现在找不到我的错误，所以不幸的是我有一个思考障碍。首先创建树的列表，然后将其传递给 isSorted 方法，然后返回错误。

% List Methode
append([], Ys, Ys).
append([X|Xs], Ys, [X|Zs]) :- append(Xs, Ys, Zs).

% inorder Traversel  - work coorect
inorder(nil, []).

inorder(tree(X, Left, Right), R) :-
   inorder(Left,R1),
   inorder(Right,R2),
   append(R1,[X|R2],R).

% contains - work coorect
contains(tree(_,L,_), X) :- contains(L,X).
contains(tree(X,_,_), X).
contains(tree(_,_,R), X) :- contains(R,X).

% isSorted
% TODO:
% Convert tree to list
% Check list whether list is correct.

% Der Fehler liegt irgendwo hier.

isSorted([]).
isSorted([_]).
isSorted(tree(X,Left,Right)) :- inorder(tree(X,Left,Right),X), isSorted(X).
isSorted([X,Y|T]) :- X=< Y, isSorted([Y|T]).




% ?-inorder(tree(5,tree(4,tree(1,nil,tree(3,tree(2,nil,nil),nil)),nil),tree(6,nil,nil)),X). -> work
% isSorted(inorder(tree(5,tree(4,tree(1,nil,tree(3,tree(2,nil,nil),nil)),nil),tree(6,nil,nil)),X)). -> doesn't work

标签： arraystreeprologinorder

解决方案

试试这个 isSorted 谓词：

isSorted([]).
isSorted([_]).

isSorted([X|[Y|_]]) :- 
    X=< Y, 
    isSorted([Y|_]).

isSorted(tree(X,Left,Right)) :- 
    inorder(tree(X,Left,Right),Z), 
    isSorted(Z).

但您的查询必须是：

?- isSorted(tree(5,tree(4,tree(1,nil,tree(3,tree(2,nil,nil),nil)),nil),tree(6,nil,nil))).

请记住，Prolog 不是函数式编程。你不能指望 p(q(X,Z)) 作为一个函数组合，如果你想要这样的东西，你需要做：

r(X):- 
    q(X,Z),
    p(Z).


还有一件事：你不能覆盖变量的值。所以，当你写

“ inorder(tree(X,Left,Right),X)” 您没有覆盖 X 的值。您要求具有根节点 X 的树使得该树的中序为 X。

推荐阅读