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

Question

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

% 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

Answer 1

试试这个 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。

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

Prolog: Convert tree to order list and check if the list is sorted

arrays

tree

prolog

inorder