Insert a node in a binary tree

tree.prolog

%planche 4
%
%Exercice 1
 
donnee(arbre1, nd(7,nd(5,nd(3,v,v),v), nd(18,nd(9, nd(8,v,v),v),nd(20,v,v)))).
donnee(arbre2, nd(3,v,nd(5,v,v))).
 
%inv(5,nd(3,v,v),Ar)
%donnee(arbre1, A), inv(12,A,Ar)).
%
inv(V1,nd(X,NL,NR), nd(X,NL,NR)):- V1 = X.
inv(V1,nd(X,v,NR), nd(X,nd(V1,v,v),NR)):- V1 < X.
inv(V1,nd(X,NL,v), nd(X,NL,nd(V1,v,v))):- V1 > X.
inv(V1,nd(X,NL,NR), nd(X,NL1,NR)):- V1 < X, inv(V1,NL,NL1).
inv(V1,nd(X,NL,NR), nd(X,NL,NR1)):- V1 > X, inv(V1,NR,NR1).
 
%tr(5,nd(3,nd(1,v,v),nd(5,v,v)))
tr(_, v):- write('No').
tr(V1, nd(V1,_,_)):- write('Yes').
tr(V1, nd(X, NL, _)):- V1 < X, tr(V1, NL).
tr(V1, nd(X, _, NR)):- V1 > X, tr(V1, NR).
 
%affinordre
affinorder(v).
affinorder(nd(X,NL,NR)):- affinorder(NL), write(X),write(' '), affinorder(NR).
 
%planche 4
%
%Exercice 1
 
donnee(arbre1, nd(7,nd(5,nd(3,v,v),v), nd(18,nd(9, nd(8,v,v),v),nd(20,v,v)))).
donnee(arbre2, nd(3,v,nd(5,v,v))).
 
%inv(5,nd(3,v,v),Ar)
%donnee(arbre1, A), inv(12,A,Ar)).
%
inv(V1,nd(X,NL,NR), nd(X,NL,NR)):- V1 = X.
inv(V1,nd(X,v,NR), nd(X,nd(V1,v,v),NR)):- V1 < X.
inv(V1,nd(X,NL,v), nd(X,NL,nd(V1,v,v))):- V1 > X.
inv(V1,nd(X,NL,NR), nd(X,NL1,NR)):- V1 < X, inv(V1,NL,NL1).
inv(V1,nd(X,NL,NR), nd(X,NL,NR1)):- V1 > X, inv(V1,NR,NR1).
 
%tr(5,nd(3,nd(1,v,v),nd(5,v,v)))
tr(_, v):- write('No').
tr(V1, nd(V1,_,_)):- write('Yes').
tr(V1, nd(X, NL, _)):- V1 < X, tr(V1, NL).
tr(V1, nd(X, _, NR)):- V1 > X, tr(V1, NR).
 
%affinordre
affinorder(v).
affinorder(nd(X,NL,NR)):- affinorder(NL), write(X),write(' '), affinorder(NR).
 
%Suppression d'un noeud de 3 cas
%Cas 1 : Sans fils
sv(V1,nd(V1,v,v),v).
%Cas 2 : Avec un fils gauche
sv(V1,nd(V1,NL,v),nd(NL,v,v)).
%Cas 3 : Avec un fils droit
sv(V1,nd(V1,v,NR),nd(NR,v,v)).
sv(X,nd(X,Fg,Fd),R) :- traitersuppression(X,nd(X,Fg,Fd),R).
traitersuppression(X,nd(X,v,Fd),Fd).
traitersuppression(X,nd(X,Fg,v),Fg).
traitersuppression(X,nd(X,Fg,Fd),Fd1) :- insttgauche(Fg,Fd,Fd1).
insttgauche(Fg,v,Fg).
insttgauche(F, nd(X,Fg,Fd),nd(X,Fg1,Fd)) :- insttgauche(F,Fg,Fg1).
 
%Profondeur arbre
profondeur(v, 0).
profondeur(nd(_,NL,NR), P):- profondeur(NL, PL), profondeur(NR,PR), PL >= PR, P is PL + 1.
profondeur(nd(_,NL,NR), P):- profondeur(NL, PL), profondeur(NR,PR), PL < PR, P is PR + 1.