Code source du tri par Arbre Binaire de Recherche
type arbre=Nil | Arbre of arbre*int*arbre;;
(* Le type arbre est défini *)
let rec ajoute_feuille abr feuille=
match abr with
|Nil->Arbre(Nil,feuille,Nil);
|Arbre(g,r,d) when r>feuille ->Arbre((ajoute_feuille g feuille),r,d) (* Insertion à gauche *)
|Arbre(g,r,d)->Arbre(g,r,(ajoute_feuille d feuille)) (* Insertion à droite *);;
(* ajoute_feuille : arbre -> int -> arbre = <fun> *)
let rec parcours_infixe abr liste=
match abr with
|Nil->[];
|Arbre(g,r,d)->
begin
(parcours_infixe g liste)@(r::parcours_infixe d liste;)
end;;
(* parcours_infixe_inverse : arbre -> 'a -> int list = <fun> *)
let rec tri_abr liste=
let rec construit_arbre ar li=
match li with
|[]->ar;
|tt::qq->ajoute_feuille (construit_arbre ar qq) tt;
in
let arbre=construit_arbre Nil liste in
parcours_infixe arbre [];;
(* tri_abr : int list -> int list = <fun> *)