Prologの技芸 3.4節の練習問題

(1)

% subtree(S,T) :-
%  SはTの部分木である．
subtree(tree(X,L,R),tree(_,Left,_)) :-
 subtree(tree(X,L,R),Left).
subtree(tree(X,L,R),tree(_,_,Right)) :-
 subtree(tree(X,L,R),Right).
subtree(tree(X,Left,Right),tree(X,Left,Right)).

(2)

% sum_tree(TreeOfIntegers,Sum) :-
%  Sumは整数の木TreeOfIntegersの整数要素の和である．
sum_tree(tree(X,Left,Right),Sum) :-
 sum_tree(Left,SumLeft),
 sum_tree(Right,SumRight),
 Sum is SumLeft+SumRight+X.
sum_tree(void,0).

(3)

% ordered(TreeOfIntegers) :-
%  TreeOfIntegersは整数の順序木である．
% ordered_left(X,Tree) :-
%  XがTreeの根節点よりも小さく，かつTreeが順序木．
% ordered_right(X,Tree) :-
%  XがTreeの根節点よりも小さく，かつTreeが順序木．
ordered(tree(X,Left,Right)) :-
 ordered_left(X,Left),
 ordered(Left),
 ordered_right(X,Right),
 ordered(Right).
ordered(void).
ordered_left(X,tree(Y,Left,Right)) :-
 X > Y, ordered_left(Y,Left), ordered_right(Y,Right).
ordered_right(X,tree(Y,Left,Right)) :-
 X < Y, ordered_left(Y,Left), ordered_right(Y,Right).
ordered_left(_,void).
ordered_right(_,void).

(4)

% tree_insert(X,Tree,Tree1) :-
%  Tree1は順序木Tree中にXを挿入してできる順序木である．
tree_insert(X,tree(X,Left,Right),tree(X,Left,Right)).
tree_insert(X,tree(Y,Left,Right),tree(Y,Left1,Right)) :-
 X < Y, tree_insert(X,Left,Left1).
tree_insert(X,tree(Y,Left,Right),tree(Y,Left,Right1)) :-
 X > Y, tree_insert(X,Right,Right1).
tree_insert(X,void,tree(X,void,void)).