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 tableau position=
  match abr with
  |Nil->();
  |Arbre(g,r,d)->
    begin
      parcours_infixe g tableau position;
      tableau.(!position)<-r;
      position:=(!position)+1;
      parcours_infixe d tableau position;
    end;;
(* val parcours_infixe : arbre -> int array -> int ref -> unit = <fun> *)

let tri_abr tableau=
  let longueur=(Array.length(tableau)-1) and abr=ref(Nil) in
  for i=0 to longueur do
    abr:=ajoute_feuille (!abr) tableau.(i);
  done;

  parcours_infixe (!abr) tableau (ref(0));;
(* val tri_abr : int array -> unit = <fun> *)