Code source du tri par Arbre Binaire de Recherche

type arbre=Nil | Arbre of arbre*int*arbre;;
(* type arbre = Nil | Arbre of arbre * int * arbre *)

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 *);;
(* val 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;;
(* val parcours_infixe : 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 [];;
(* val tri_abr : int list -> int list = <fun> *)