代写INF F5、代做Java设计程序

日期：2025-01-08 09:19

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) {…}

}