TD5 - Parcours d'arbres binaires non entiers

(* TD n°5 : parcours d'arbres *)

type ('f, 'n) abe =
|Feuille of 'f
|Noeud of 'n * ( ('f,'n) abe)*(('f,'n) abe);;

type 'a tree =
|Vide
|Node of 'a * ('a tree) * ('a tree);;

(* Exercice 1 *)
let toto =
Node(   1,
        Node(   2,
                Node( 4,Vide,Vide),
                Node(   5,
                        Node(7,Vide,Vide),
                        Node(8,Vide,Vide))),
        Node( 3,
                Vide,
                Node(   6,
                        Node(9,Vide,Vide),
                        Vide)));;
(* Exercice 2 *)
let rec abe_to_tree abe = match abe with
|Feuille f -> Node(f,Vide,Vide)
|Noeud (n,fg,fd) -> Node(n,abe_to_tree fg,abe_to_tree fd);;

let exemple1 =
Noeud(  1,
        Noeud(  2,
                Feuille 4,
                Noeud(  5,
                        Feuille 7,
                        Feuille 8)),
        Noeud( 3,
                Feuille 0,
                Noeud(  6,
                        Feuille 9,
                        Feuille 0)));;
abe_to_tree exemple1;;


(* Exercice 3 *)

let rec parcours_prefixe tree = match tree with
|Vide -> []
|Node (a,Vide,Vide) -> [a]
|Node (a,fg,Vide) -> a::(parcours_prefixe fg)
|Node (a,Vide,fd) -> a::(parcours_prefixe fd)
|Node (a,fg,fd) -> a::((parcours_prefixe fg)@(parcours_prefixe fd));;

parcours_prefixe toto;;









(* Exercice 4 *)

let rec parcours_suffixe tree = match tree with
|Vide -> []
|Node (a,Vide,Vide) -> [a]
|Node (a,fg,Vide) -> (parcours_infixe fg)@[a]
|Node (a,Vide,fd) -> (parcours_infixe fd)@[a]
|Node (a,fg,fd) -> let (g,d) = (parcours_infixe fg,parcours_infixe fd) in (g@d)@[a];;
parcours_suffixe toto;;


let rec parcours_infixe tree = match tree with
|Vide -> []
|Node (a,Vide,Vide) -> [a]
|Node (a,fg,Vide) -> (parcours_infixe fg)@[a]
|Node (a,Vide,fd) -> [a]@(parcours_infixe fd)
|Node (a,fg,fd) -> let (g,d) = (parcours_infixe fg,parcours_infixe fd) in g@[a]@d;;
parcours_infixe toto;;


(* Exercice 5 *)

let parcours_largeur tree =
    let rec aux liste_of_tree liste_parcourue = match liste_of_tree with
    |[] -> List.rev liste_parcourue
    |(Node (n,Vide,Vide))::t -> aux t (n::liste_parcourue)
    |(Node (n,Vide,fd))::t -> aux (t@[fd]) (n::liste_parcourue)
    |(Node (n,fg,Vide))::t -> aux (t@[fg]) (n::liste_parcourue)
    |(Node (n,fg,fd))::t -> aux (t@([fg]@[fd])) (n::liste_parcourue)
    in aux [tree] [];;

parcours_largeur toto;;