L3 MIASHS
INF F5 — PROGRAMMATION AVANCEE ET STRUCTURES DE
DONNEES
Seconde chance — Juin 2024
Notes de cours, TD et TM autorisés — durée 3 heures
Le barème indiqué est indicatif et peut légèrement varier lors de la correction. Ce barème est sur 23
points, la note finale sera le minimum entre la note obtenue selon ce barème et 20. Lorsque des
définitions de la même méthode sont demandées sur plusieurs classes, rappeler le nom de la classe
concernée en commentaire.
Sujet de programmation : arbres n-aires
Nous nous intéressons à la manipulation d’arbres n-aires, c’est-à-dire d’arbres dans lesquels les nœuds
peuvent admettre un nombre quelconque de nœuds enfants. On choisit de les implémenter par des nœuds
possédant deux références comme le montre la figure ci-dessous. A gauche, un arbre n-aire est représenté à
l’aide de nœuds pouvant porter plusieurs références enfant. A droite, le même arbre est représenté par des
nœuds portant au plus une référence premierEnfant et au plus une référence frereSuivant.
1 Constructeurs (1 point)
1.1 (0,5 pt) Donner la définition du constructeur de la classe Noeud. Toutes les valeurs sont possibles
pour les 3 attributs et en particulier null est autorisé.
1.2 (0,5 pt) Donner la définition du constructeur de la classe Arbre. Ce constructeur permet d’obtenir un
arbre vide, sans racine.
2 Accesseurs et méthodes simples (2 points)
2.1 (0,5 pt) Donner la définition de l’accesseur en lecture getValeur() de la classe Noeud.
2.2 (1 pt) Donner la définition de la méthode estVide() de la classe Arbre qui retourne true si est
seulement si this est vide, c’est-à-dire qu’il n’a pas de racine.
2.3 (0,5 pt) Donner la définitions de la méthode getValeurRacine() de la classe Arbre qui retourne
la valeur portée par la racine de this. Cette méthode lève une ArbreException si this est vide.
3 Recherche de nœud (2 points)
3.1 (2 pt) Donner la définition de la méthode getNoeud(E valeur) de la classe Noeud qui retourne le
nœud portant la première occurrence de valeur (au sens de la méthode equals()) dans les nœuds
du sous-arbre issu de this, ou null si cette valeur n’est pas trouvée. La recherche s’effectue en
profondeur d’abord et doit être indépendante la méthode enfants().
premierEnfant
frereSuivant
4 Reconnaissance des feuilles (2 points)
4.1 (0,5 pt) Donner la définition de la méthode estFeuille() de la classe Noeud qui retourne true si
est seulement this est une feuille, c’est-à-dire un nœud sans enfants.
4.2 (1,5 pt) Donner la définition de la méthode estFeuille(E val) de la classe Arbre. Cette méthode
retourne true si est seulement si la première occurrence de val dans this est portée par une feuille.
Si this ne porte aucune occurrence de val, cette méthode lève une ArbreException.
5 Gestion des enfants directs (7 points)
5.1 (1,5 pt) Donner la définition de la méthode getEnfantAt(int i) de la classe Noeud qui retourne
l’enfant d’indice i parmi les enfants de this. Les enfants sont indicés à partir de 0. Cette méthode
lève une IndexOutOfBoundsException si l’indice fourni est invalide. Cette méthode doit être
indépendante de la méthode enfants().
5.2 (1 pt) Donner la définition de la méthode getEnfantAt(E valParent, int i) de la classe Arbre
qui retourne la valeur portée par l’enfant d’indice i de la première occurrence de valParent dans
this. Cette méthode lève une ArbreException si this ne porte aucune occurrence de valParent.
5.3 (1 pt) Donner la définition de la méthode getNombreEnfants() de la classe Noeud qui retourne le
nombre d’enfants de this. Cette méthode doit être indépendante de la méthode enfants().
5.4 (1 pt) Donner la définition de la méthode getNombreEnfants(E valParent) de la classe Arbre
qui retourne le nombre d’enfants de la première occurrence de valParent dans this. Cette méthode
lève une ArbreException si this ne porte aucune occurrence de valParent.
5.5 (1,5 pt) Donner la définition de la méthode getIndiceEnfant(E valEnfant) de la classe Noeud
qui retourne l’indice du premier enfant de this portant une valeur équivalente à valEnfant, ou -1
si un tel enfant n’existe pas. Cette méthode doit être indépendante de la méthode enfants().
5.6 (1 pt) Donner la définition de la méthode getIndiceEnfant(E valParent, E valEnfant) de
la classe Arbre qui retourne l’indice du premier enfant de la première occurrence de valParent dans
this qui porte une valeur équivalente à valEnfant. Cette méthode lève une ArbreException si
this ne porte aucune occurrence de valParent.
6 Listes (4 points)
6.1 (1 pt) Donner la définition de la méthode enfants() de la classe Noeud qui retourne une liste
contenant les enfants de this.
6.2 (2 pt) Donner la définition de la méthode descendants() de la classe Noeud qui retourne une liste
contenant tous les descendants de this, y compris this lui-même.
6.3 (1 pt) Donner la définition de la méthode noeuds() de la classe Arbre qui retourne une liste
contenant tous les nœuds de this.
7 Ajout (5 points)
7.1 (1,5 pt) Donner la définition de la méthode ajouteEnfant(E val) de la classe Noeud qui permet
d’ajouter à this un nouveau nœud portant la valeur val comme dernier enfant.
7.2 (2 pt) Donner la définition de la méthode ajout(E val, List<E> chemin) de la classe Noeud
qui permet d’ajouter un nouveau nœud portant la valeur val dans le sous-arbre issu de this. chemin
permet de naviguer dans ce sous-arbre :
- si chemin est vide, on ajoute le nouveau nœud comme dernier enfant de this ;
- si le premier élément de chemin est une valeur portée par l’un des enfants de this, l’ajout
est effectué dans le sous-arbre issu de cet enfant en tenant compte du reste de chemin ;
- si le premier élément de chemin n’est pas une valeur portée par l’un des enfants de this, un
nouveau nœud portant cette valeur est ajouté comme dernier enfant de this et l’ajout est
effectué dans le sous-arbre issu de ce nouveau nœud en tenant compte du reste de chemin.
7.3 (0,5 pt) Donner la définition de la méthode nouvelleRacine(E val) de la classe Arbre qui permet
d’ajouter une nouvelle racine portant la valeur val à this. L’ancienne racine devient enfant de la
nouvelle racine.
7.4 (1 pt) Donner la définition de la méthode ajout(E val, List<E> chemin) de la classe Arbre
qui permet d’ajouter dans this un nouveau nœud portant la valeur val comme dernier enfant du
nœud désigné par chemin. Si this est vide, cette méthode lève une ArbreException.
2/3
3/3
8 Squelettes de programmes
package nAires;
import java.util.*;
public interface NoeudNAire<E> {
E getValeur();
NoeudNAire<E> getNoeud(E valeur);
boolean estFeuille();
NoeudNAire<E> getEnfantAt(int i);
int getNombreEnfants();
int getIndiceEnfant(E valEnfant);
List<NoeudNAire<E>> enfants();
List<NoeudNAire<E>> descendants();
void ajout(E val, List<E> chemin);
}
package nAires;
public class ArbreException extends RuntimeException {
public ArbreException() {}
public ArbreException(String message) {
super(message);
}
}
package nAires;
import java.util.*;
public class Noeud<E> implements NoeudNAire<E> {
private Noeud<E> premierEnfant, frereSuivant;
private E valeur;
public Noeud(E valeur, Noeud<E> premierEnfant, Noeud<E> frere) {…}
public E getValeur() {…}
public NoeudNAire<E> getNoeud(E valeur) {…}
public boolean estFeuille() {…}
public NoeudNAire<E> getEnfantAt(int i) {…}
public int getNombreEnfants() {…}
public int getIndiceEnfant(E valEnfant) {…}
public List<NoeudNAire<E>> enfants() {…}
public List<NoeudNAire<E>> descendants() {…}
private Noeud<E> ajouteEnfant(E val) {…}
public void ajout(E val, List<E> chemin) {…}
}
package nAires;
import java.util.*;
public class Arbre<E> {
private NoeudNAire<E> racine;
public Arbre() {…}
public boolean estVide() {…}
public E getValeurRacine() {…}
public boolean estFeuille(E val) {…}
public E getEnfantAt(E valParent, int i) {…}
public int getNombreEnfants(E valParent) {…}
public int getIndiceEnfant(E valParent, E valEnfant) {…}
public List<NoeudNAire<E>> noeuds() {…}
public void nouvelleRacine(E val) {…}
public void ajout(E val, List<E> chemin) {…}
}
請加QQ：99515681 郵箱：99515681@qq.com WX：codinghelp
