Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
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().
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 siest 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.
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) {…}
}
|