#open "graphics";;
open_graph "";;

type 'a arbre = vide | N of 'a arbre * 'a * 'a arbre ;;

let draw_arbre string_of equ arbre =

        let rec hauteur = fun
                | vide -> 0
                | (N(g,_,d)) -> 1 + max (hauteur g) (hauteur d)
        in

        let rec taille = fun
                | vide -> 0
                | (N(g,_,d)) -> 1 + (taille g) + (taille d)
        in

        let p = fun
                | vide -> 0
                | (N(vide,_,vide)) -> 50
                | (N(_,_,vide)) -> 85
                | (N(vide,_,_)) -> 15
                | (N(g,_,d)) -> let t = taille g in t * 100 / (t + (taille d))
        in

        let rec puiss a n =
                if n = 0 then 1 else (
                        let b = puiss (a*a) (n/2) in
                        if n mod 2 = 0 then b else a*b;
                );
        in

        let sx = size_x() and sy = size_y() and mx = 50 and my = 100
        and t = hauteur arbre in

        let x i j xp plage p gd =
                if equ then (if gd then xp-(sx-2*mx)*plage*(100-p)/10000
                                   else xp+(sx-2*mx)*plage*p/10000)
                       else mx+(sx-2*mx)*(2*i-1)/(puiss 2 (j+1))

        and y j = sy-my-(sy-2*my)*j/(t-1) in

        let rec parcours a i j xp plage_g plage_d = match a with
                | vide -> ()
                | N(g,r,d) -> (
                        let xp = x i j xp 0 0 true
                        and s = string_of r in
                        let l = string_length s in
                        moveto (xp-l*4) ((y j)-9);
                        draw_string s;
                        if g <> vide then (
                                moveto xp ((y j)-10);
                                let pg = p g in
                                let xg = x (2*i-1) (j+1) xp plage_g pg true in
                                lineto xg ((y (j+1))+10);
                                let plage = plage_g*pg/100 in
                                parcours g (2*i-1) (j+1) xg plage (plage_g-plage);
                        );
                        if d <> vide then (
                                moveto xp ((y j)-10);
                                let pd = p d in
                                let xd = x (2*i) (j+1) xp plage_d pd false in
                                lineto xd ((y (j+1))+10);
                                let plage = plage_d*pd/100 in
                                parcours d (2*i) (j+1) xd plage (plage_d-plage);
                        );
                )
        in

        let pp = p arbre in
        parcours arbre 1 0 (x 1 0 mx 100 pp false) pp (100-pp);
;;

let draw_arbre_i = draw_arbre string_of_int ;;
let draw_arbre_c = draw_arbre string_of_char ;;
let draw_arbre_s = draw_arbre (fun x -> x) ;;