Université M’Hamed Bougara de Boumerdes 2024-2025
Faculté des sciences - Département d’informatique Promotion : Master 1 Module : PFA
Série 4 : Arbres binaires
Partie TD
Exercice 01: arbres et arbres ordonnés
Un arbre binaire non vide est compose d'une racine et de deux arbres binaires appelés sous-arbre
droit et sous-arbre gauche. On définit en Ocaml le type 'a arbin de la façon suivante :
type 'a arbin = Bin of ('a arbin * 'a * 'a arbin) | Vide ;;
1- Représenter par un schéma les arbres : a) Bin(Bin(Vide, 5, Vide), 3, Vide) ; b)
Bin(Bin(Vide, 0, Vide), 2, Bin(Vide, 9, Vide)) ;
c) Bin (Bin (Bin (Vide, 5, Vide), 3, Vide), 6, Bin (Bin (Vide, 0, Vide), 2, Bin (Vide, 9,
Vide)))
2- Le parcours infixe d'un arbre binaire consiste à effectuer dans l'ordre :
le parcours infixe du sous-arbre gauche
le parcours de la racine
le parcours infixe du sous-arbre droit
Par exemple le parcours infixe de l'arbre t1 produit la liste [5; 3; 6; 0; 2; 9].
Écrire une fonction infixe : 'a arbin -> 'a list qui produit la liste des éléments d'un arbre binaire selon
un parcours infixe.
2. On dit qu'un arbre binaire est ordonné si et seulement si, soit c'est l'arbre vide, soit les
conditions suivantes sont vérifiées :
les sous-arbres droit et gauche sont ordonnés
la racine est supérieure ou égale a tous les éléments du sous-arbre gauche et strictement
inférieure a tous les éléments du sous-arbre droit.
Remarquons que le parcours infixe d'un arbre binaire ordonne fournit une liste ordonné. Par exemple
le parcours infixe de l'arbre ordonné t suivant : produit la liste [1 ;2 ;4 ;6 ;6 ;10 ;14]
L'insertion d'un élément dans un arbre binaire ordonné consiste a ajouter cet élément de facon a
obtenir un arbre binaire ordonné. L'élément ajoute devient une feuille de l'arbre. Par exemple si l'on
veut insérer l'élément 12 a l'arbre binaire ordonné précédent on obtient l'arbre ordonné
Écrire une fonction insere : 'a -> 'a arbin -> 'a arbin. Cette fonction prend comme données un élément
et un arbre binaire ordonné, et insère l'élément dans l'arbre binaire de telle facon que le résultat soit un
arbre binaire ordonné.
Université M’Hamed Bougara de Boumerdes 2024-2025
Faculté des sciences - Département d’informatique Promotion : Master 1 Module : PFA
La méthode de tri proposée consiste a partir d'une liste d'entiers a construire un arbre binaire
ordonné par des insertions successives des éléments de la liste, puis a parcourir l'arbre suivant
un parcours infixe. Écrire une fonction insere_liste: 'a list -> 'a arbre. Cette fonction prend en
argument une liste et produit un arbre binaire ordonné par des insertions successives de tous
les éléments de la liste.
Écrire une fonction tri : 'a list -> 'a list qui trie une liste donnée. Pour cela on utilisera les fonctions
insere_liste et infixe.
Exercice 02
Soit le type 'a arbin défini comme suit:
type 'a arbin = Bin of ('a arbin * 'a * 'a arbin) | Vide ;;
1- Ecrire une fonction récursive qui, à partir d'un arbre d'entiers, retourne directement deux listes
telles que: la première liste contient les éléments pairs de l'arbre et la deuxième liste contient
les éléments impairs. Donner le type de cette fonction.
2- On souhaite généraliser la fonction de la question 1 pour prendre en compte des propriétés P
quelconques . Ecrire une fonction récursive qui, à partir d'un arbre, permet de retourner deux
listes telles que : la première contient les éléments de l'arbre qui satisfont la propriété P et la
deuxième contient les éléments qui ne satisfont pas la propriété P.
3- Donner le type de cette fonction.
Partie TP
Exercice 01: arbre caduc
Nous considérons le type suivant :
Type arbre_caduc =
FeuilleVerte
| FeuilleJaune
| Branche of arbre_caduc * arbre_caduc ;;
1. Étant donné deux arbres de type arbre_caduc, écrire une fonction qui teste si les deux arbres ont la
même structure (la couleur des feuilles n'a pas d'importance).
2. Étant donné un arbre de type arbre_caduc, écrire une fonction (et une seule) compte_feuilles qui
renvoie le nombre de feuilles de cet arbre (la couleur des feuilles n'a pas d'importance)
Université M’Hamed Bougara de Boumerdes 2024-2025
Faculté des sciences - Département d’informatique Promotion : Master 1 Module : PFA
