% Ex1:
arc(a,b,2).
arc(a,g,6).
arc(b,e,2).
arc(b,c,7).
arc(g,e,1).
arc(g,h,4).
arc(e,f,2).
arc(f,c,3).
arc(f,h,2).
arc(c,d,3).
arc(h,d,2).
chemin(X,Y,cons(X,Y)) :- arc(X,Y,_).
chemin(X,Y,cons(X,W)) :- arc(X,Z,_),chemin(Z,Y,W).

%Test cases
% chemin(X,Y,C)
% chemin(a,X,C).
% chemin(X,g,C).
% chemin(a,Y,cons(a,cons(_,Y))).


% Ex2: (issu des 99 pb)
% P54: Write a predicate istree/1 which succeeds if and only if its argument
%      is a Prolog term representing a binary tree.
%
% istree(T) :- T is a term representing a binary tree (i), (o)

istree(nil).
istree(t(_,L,R)) :- istree(L), istree(R).


% Test cases (can be used for other binary tree problems as well)

% tree(1,t(a,t(b,t(d,nil,nil),t(e,nil,nil)),t(c,nil,t(f,t(g,nil,nil),nil)))).
% tree(2,t(a,nil,nil)).
% tree(3,nil).


% Ex3: (issu des 99 pb)
 
% P56 (**) Symmetric binary trees 
% Let us call a binary tree symmetric if you can draw a vertical 
% line through the root node and then the right subtree is the mirror
% image of the left subtree.
% Write a predicate symmetric/1 to check whether a given binary
% tree is symmetric. Hint: Write a predicate mirror/2 first to check
% whether one tree is the mirror image of another.

% symmetric(T) :- the binary tree T is symmetric.

symmetric(nil).
symmetric(t(_,L,R)) :- mirror(L,R).

mirror(nil,nil).
mirror(t(_,L1,R1),t(_,L2,R2)) :- mirror(L1,R2), mirror(R1,L2).