cm3-code.ml

type 'a arbre_bin_g =
  | ABGVide
  | ABGNoeud of 'a * 'a arbre_bin_g * 'a arbre_bin_g

(** Version naive du contenu d'un arbre binaire *)
let rec contenu_naif (arb : 'a arbre_bin_g) : 'a list =
  match arb with
  | ABGVide -> []
  | ABGNoeud (e, fg, fd) -> contenu_naif fg @ (e :: contenu_naif fd)

let a1 = ABGNoeud (1, ABGVide, ABGVide)
let a2 = ABGNoeud (9, ABGVide, ABGVide)
let a3 = ABGNoeud (3, ABGVide, ABGVide)
let a4 = ABGNoeud (7, ABGVide, ABGVide)
let a5 = ABGNoeud (2, a1, a3)
let a6 = ABGNoeud (8, a4, a2)
let a7 = ABGNoeud (5, a5, a6);;

contenu_naif a7

(** [ajoute_contenu arb l] ajoute les élements de arb en tête des éléments de la
    liste l *)
let rec ajoute_contenu (arb : 'a arbre_bin_g) (l : 'a list) : 'a list =
  match arb with
  | ABGVide -> l
  | ABGNoeud (e, fg, fd) ->
      let l_fd = ajoute_contenu fd l in
      let l_e_fd = e :: l_fd in
      ajoute_contenu fg l_e_fd

let contenu (arb : 'a arbre_bin_g) : 'a list = ajoute_contenu arb []