TD n° 5 : Arbres

In [1]:
type ('f, 'n) arbre =
    | Feuille of 'f
    | NoeudInterne of ('f, 'n) arbre * 'n * ('f, 'n) arbre
;;
Out[1]:
type ('f, 'n) arbre =
    Feuille of 'f
  | NoeudInterne of ('f, 'n) arbre * 'n * ('f, 'n) arbre

Exercice 1

In [2]:
let arbre =
  NoeudInterne (Feuille 2, 1, NoeudInterne (Feuille 4, 3, Feuille 5))
;;
Out[2]:
val arbre : (int, int) arbre =
  NoeudInterne (Feuille 2, 1, NoeudInterne (Feuille 4, 3, Feuille 5))

Exercice 2

In [3]:
let rec symetrique arbre =
  match arbre with
  | Feuille _ -> arbre
  | NoeudInterne (fils_gauche, noeud, fils_droit) ->
    NoeudInterne (symetrique fils_droit, noeud, symetrique fils_gauche)
;;
Out[3]:
val symetrique : ('a, 'b) arbre -> ('a, 'b) arbre = <fun>
In [4]:
symetrique arbre;;
Out[4]:
- : (int, int) arbre =
NoeudInterne (NoeudInterne (Feuille 5, 3, Feuille 4), 1, Feuille 2)

Exercice 3

1.

In [5]:
let rec initialise_complet n val_f val_n =
  match n with
  | 0 -> Feuille val_f
  | _ -> let arbre = initialise_complet (n - 1) val_f val_n in
	 NoeudInterne (arbre, val_n, arbre)
;;
Out[5]:
val initialise_complet : int -> 'a -> 'b -> ('a, 'b) arbre = <fun>
In [6]:
initialise_complet 2 1 0;;
Out[6]:
- : (int, int) arbre =
NoeudInterne (NoeudInterne (Feuille 1, 0, Feuille 1), 0,
 NoeudInterne (Feuille 1, 0, Feuille 1))

2. Un arbre complet de hauteur $n$ a $2^n$ feuilles de profondeur $n$ chacune. Son cheminement est donc de $n2^n$.

Exercice 4

1.

In [7]:
let rec strahler arbre =
    match arbre with
    | Feuille _ -> 1
    | NoeudInterne(fils_gauche, _, fils_droit) ->
        let s_g = strahler fils_gauche in
        let s_d = strahler fils_droit in
        if s_g = s_d then
            s_g + 1
        else
            max s_g s_d
;;
Out[7]:
val strahler : ('a, 'b) arbre -> int = <fun>
In [8]:
let arbre2 = 
    let sous_arbre = initialise_complet 2 0 0 in
    NoeudInterne(
        NoeudInterne(
            sous_arbre,
            0,
            NoeudInterne(
                sous_arbre,
                0,
                Feuille 0
                )
            ),
        0, 
        Feuille 0
        )
;;
Out[8]:
val arbre2 : (int, int) arbre =
  NoeudInterne
   (NoeudInterne
     (NoeudInterne (NoeudInterne (Feuille 0, 0, Feuille 0), 0,
       NoeudInterne (Feuille 0, 0, Feuille 0)),
     0,
     NoeudInterne
      (NoeudInterne (NoeudInterne (Feuille 0, 0, Feuille 0), 0,
        NoeudInterne (Feuille 0, 0, Feuille 0)),
      0, Feuille 0)),
   0, Feuille 0)
In [9]:
strahler arbre2;;
Out[9]:
- : int = 4

2. Par récurrence sur $h\in\mathbb N$.

  • Initialisation : Si on considère un arbre de hauteur $0$, la racine est une feuille et le nombre de Strahler est $1=h+1$ avec un arbre qui est bien complet.
  • Hérédité : Si le résultat est vrai pour un $h\geqslant0$, et si on a un arbre de hauteur $h+1$, en notant $s$ son nombre de Strahler, considérons $s_g$ et $s_d$ les nombres de Strahler des fils gauche et droit de la racine. Comme ce sont des arbres de hauteur au plus $h$, par hypothèse de récurrence, $s_g\leqslant h+1$ et $s_d\leqslant h+1$. Alors $s\in\{s_g + 1, max(s_g, s_d)\}$ donc $s_g\leqslant h + 2$. De plus, il y a égalité si et seulement si $s = s_g + 1$ si et seulement si $s_g = s_d = h + 1$ si et seulement si les fils gauche et droit sont complets de hauteur $h$ (par hypothèse de récurrence) si et seulement si l'arbre est complet, ce qui établit la récurrence.

On peut aussi raisonner par induction structurelle.

3. Un arbre de hauteur $h\neq0$ possède au moins un noeud interne, donc au moins un noeud avec deux feuilles qui aura $2$ comme nombre de Strahler. Comme le nombre de Strahler d'un noeud est toujours au moins aussi grand que ceux de ses fils, un arbre de hauteur $h\neq0$ a bien un nombre de Strahler au moins égal à $2$.

De plus, ce nombre sera égal à $2$ si et seulement si tous les noeuds internes ont un nombre de Strahler de $2$ (toujours vu la propriété de croissance). Cela signifie que chaque noeud interne doit avoir un fils dont le nombre de Strahler vaut $1$ et un fils dont le nombre de Strahler vaut $2$, ce qui correspond bien au type d'arbre décrit dans la question.

Exercice 5

In [10]:
type ('f, 'n) noeud = F of 'f | NI of 'n;;
Out[10]:
type ('f, 'n) noeud = F of 'f | NI of 'n

1. NoeudInterne code à l'arbre (triplet (fils gauche, étiquette, fils droit)) issu du noeud alors que NI code seulement à l'étiquette du noeud.

2.

  • Arbre 1
    • Parcours prefixe : [NI 1; F 2; NI 3; F 4; F 5]
    • Parcours infixe : [F 2; NI 1; F 4; NI 3; F 5]
    • Parcours postfixe : [F 2; F 4; F 5; NI 3; NI 1]
  • Arbre 2
    • Parcours prefixe : [NI 1; NI 3; F 5; F 4; F 2]
    • Parcours infixe : [F 5; NI 3; F 4; NI 1; F 2]
    • Parcours postfixe : [F 5; F 4; NI 3; F 2; NI 1]

3.

In [11]:
let rec parcours_prefixe arbre =
    match arbre with
    | Feuille f -> [F f]
    | NoeudInterne(fils_gauche, noeud, fils_droit) ->
    (NI noeud) :: (parcours_prefixe fils_gauche) @ (parcours_prefixe fils_droit)
;;
Out[11]:
val parcours_prefixe : ('a, 'b) arbre -> ('a, 'b) noeud list = <fun>
In [12]:
parcours_prefixe arbre;;
Out[12]:
- : (int, int) noeud list = [NI 1; F 2; NI 3; F 4; F 5]
In [13]:
parcours_prefixe (symetrique arbre);;
Out[13]:
- : (int, int) noeud list = [NI 1; NI 3; F 5; F 4; F 2]

Version sans @ (liste chaînée utilisée comme pile)

In [14]:
let parcours_prefixe_bis arbre =
    (* (parcours_prefixe arbre) @ liste est un invariant de aux *)
    let rec aux arbre liste =
        match arbre with
        | Feuille f -> (F f) :: liste
        | NoeudInterne(fils_gauche, noeud, fils_droit) ->
        (NI noeud) :: (aux fils_gauche (aux fils_droit liste))
    in
    aux arbre []
;;
Out[14]:
val parcours_prefixe_bis : ('a, 'b) arbre -> ('a, 'b) noeud list = <fun>
In [15]:
parcours_prefixe_bis arbre;;
Out[15]:
- : (int, int) noeud list = [NI 1; F 2; NI 3; F 4; F 5]
In [16]:
parcours_prefixe_bis (symetrique arbre);;
Out[16]:
- : (int, int) noeud list = [NI 1; NI 3; F 5; F 4; F 2]

4.

Chaque concaténation a un coût de $O(n)$ et il y a $n$ noeuds visités une et une seule fois donc la complexité est en $O(n^2)$. Cette complexité est atteinte lorsque chaque noeud interne a pour fils droit une feuille.

5.

In [17]:
let rec parcours_infixe arbre =
    match arbre with
    | Feuille f -> [F f]
    | NoeudInterne(fils_gauche, noeud, fils_droit) ->
    (parcours_infixe fils_gauche) @ ((NI noeud) :: parcours_infixe fils_droit)
;;
Out[17]:
val parcours_infixe : ('a, 'b) arbre -> ('a, 'b) noeud list = <fun>
In [18]:
parcours_infixe arbre;;
Out[18]:
- : (int, int) noeud list = [F 2; NI 1; F 4; NI 3; F 5]
In [19]:
parcours_infixe (symetrique arbre);;
Out[19]:
- : (int, int) noeud list = [F 5; NI 3; F 4; NI 1; F 2]
In [20]:
let parcours_infixe_bis arbre =
    (* (parcours_infixe arbre) @ liste est un invariant de aux *)
    let rec aux arbre liste =
        match arbre with
        | Feuille f -> (F f) :: liste
        | NoeudInterne(fils_gauche, noeud, fils_droit) ->
       aux fils_gauche ((NI noeud) :: (aux fils_droit liste))
    in
    aux arbre []
;;
Out[20]:
val parcours_infixe_bis : ('a, 'b) arbre -> ('a, 'b) noeud list = <fun>
In [21]:
parcours_infixe_bis arbre;;
Out[21]:
- : (int, int) noeud list = [F 2; NI 1; F 4; NI 3; F 5]
In [22]:
parcours_infixe_bis (symetrique arbre);;
Out[22]:
- : (int, int) noeud list = [F 5; NI 3; F 4; NI 1; F 2]
In [23]:
let rec parcours_suffixe arbre =
    match arbre with
    | Feuille f -> [F f]
    | NoeudInterne(fils_gauche, noeud, fils_droit) ->
    (parcours_suffixe fils_gauche) @ (parcours_suffixe fils_droit) @ [NI noeud]
;;
Out[23]:
val parcours_suffixe : ('a, 'b) arbre -> ('a, 'b) noeud list = <fun>
In [24]:
parcours_suffixe arbre;;
Out[24]:
- : (int, int) noeud list = [F 2; F 4; F 5; NI 3; NI 1]
In [25]:
parcours_suffixe (symetrique arbre);;
Out[25]:
- : (int, int) noeud list = [F 5; F 4; NI 3; F 2; NI 1]
In [26]:
let parcours_suffixe_bis arbre =
    (* (parcours_infixe arbre) @ liste est un invariant de aux *)
    let rec aux arbre liste =
        match arbre with
        | Feuille f -> (F f) :: liste
        | NoeudInterne(fils_gauche, noeud, fils_droit) ->
       aux fils_gauche ( aux fils_droit ((NI noeud) :: liste))
    in
    aux arbre []
;;
Out[26]:
val parcours_suffixe_bis : ('a, 'b) arbre -> ('a, 'b) noeud list = <fun>
In [27]:
parcours_suffixe_bis arbre;;
Out[27]:
- : (int, int) noeud list = [F 2; F 4; F 5; NI 3; NI 1]
In [28]:
parcours_suffixe (symetrique arbre);;
Out[28]:
- : (int, int) noeud list = [F 5; F 4; NI 3; F 2; NI 1]

6. On trouve l'arbre :
. 1 / \ 2 4 / \ 4 5

In [29]:
NoeudInterne (NoeudInterne (Feuille 4, 2, Feuille 5), 1, Feuille 4)
Out[29]:
- : (int, int) arbre =
NoeudInterne (NoeudInterne (Feuille 4, 2, Feuille 5), 1, Feuille 4)

7.

In [30]:
let reconstruire_prefixe liste_parcours =
    (* Renvoie l'arbre construit à partir du début de la 
       liste et la liste de ce qu'il reste à construire *)
    let rec construction_partielle liste =
    match liste with
    | [] -> failwith "Cette liste ne correspond pas à un parcours préfixe d'un arbre"
    | (F f) :: suite -> (Feuille f, suite)
    | (NI n) :: suite ->
        let fils_gauche, suite_apres_gauche = construction_partielle suite in
        let fils_droit, suite_apres_droit = construction_partielle suite_apres_gauche in
        (NoeudInterne (fils_gauche, n, fils_droit), suite_apres_droit)
    in 
    let resultat, reste = construction_partielle liste_parcours in
    match reste with
    | [] -> resultat
    | _ -> failwith "Cette liste ne correspond pas à un parcours préfixe d'un arbre"
;;
Out[30]:
val reconstruire_prefixe : ('a, 'b) noeud list -> ('a, 'b) arbre = <fun>
In [31]:
reconstruire_prefixe [NI 1; F 2; NI 3; F 4; F 5];;
Out[31]:
- : (int, int) arbre =
NoeudInterne (Feuille 2, 1, NoeudInterne (Feuille 4, 3, Feuille 5))
In [32]:
reconstruire_prefixe [NI 1; NI 3; F 5; F 4; F 2];;
Out[32]:
- : (int, int) arbre =
NoeudInterne (NoeudInterne (Feuille 5, 3, Feuille 4), 1, Feuille 2)
In [33]:
reconstruire_prefixe [F 5; F 4; NI 3; F 2; NI 1];;
Out[33]:
Exception:
Failure
 "Cette liste ne correspond pas \195\160 un parcours pr\195\169fixe d'un arbre".

8. Les arbres suivants ont même parcours infixe.

. 1 / \ 2 5 / \ 3 4

et

. 2 / \ 3 1 / \ 4 5