Exercice 2
Une classe Tree implémente des arbres dont les noeuds (noeuds internes ou feuilles) contiennent une donnée de nom data (un int) et ont un nombre quelconque de fils.Pour éviter de stocker une liste de fils dans les noeuds sans fils (les feuilles),on utilise 2 classes Leaf et InternalNode.
La classe Leaf représente les noeuds sans fils ayant un ou plusieurs fils .Dans les noeuds internes ,les fils sont représentés par un champ children de type List<Node>.
La classe Tree comprend
public class Tree {
private final Node root;
public String toString() { return root.toString();}
public int size() { return root.size();}
public boolean contains(int i) { return root.contains(i);}
...........
}
1)Expliquer brièvement pourquoi on a besoin d'un super-type Node
2)Doit-on utiliser une interface ou une classe abstraite pour représenter le super-type Node?Justifier votre choix.
3)Expliquer pourquoi il faut un constructeur dans la classe Tree qui prend en ragument la racine de l'arbre.Écrire le code correspondant.
4)Indiquer l'ensemble des modificateurs de visibilité possibles pour la méthode size() de Node.
5)Écrire les autres classes (déclarations ,champs et constructeurs).Attention aux modificateurs de visibilité.Par exemple le code suivant
List<Node> listThree = new ArrayList<Node>();
listThree.add(new Leaf(5));
listThree.add(new Leaf(6));
List<Node> listOne = new LinkedList<Node>();
listOne.add(new InternalNode(3,listThree));
listOne.add(new Leaf(4));
Node one = new InternalNode(1,listOne);
Tree tree = new Tree(one);
crée l'arbre ci-dessous(l'arbre est comme cela:
l'arbre a pour racine 1 qui a trois fils 2,3,4(de gauche a droite), 3 a deux fils 5 et 6 )
6)Écrire une méthode size() dans la classe Tree.La taille d'un arbre est son nombre de noeuds.
Indiquer le code des méthodes à ajouter dans les autres classes.Utiliser l'annotation @Override.
7)Expliquer pourquoi le constructeur d'InternalNode peut priendre en paramètre une List<?extends Node>.
8)Écrire une méthode boolean contains(int i) dans la classe Tree.Cette méthode renvoie true si l'arbre contient un noeud dont la valeur du cham est data est i.Indiquer le code des méthodes à ajouter dans les autres classes.
9)Écrire une méthode toString() dans la classe Tree.Cette méthode renvoie une forme préfixe de l'arbre.Sur l'exemple ci-dessus,on obtient 1 2 3 4 5 6.Indiquer le code des méthodes à ajouter dans les autres classes.
10)Écrire une méthode boolean equals(Object o) dans la classe Tree.Cette méthode teste si l'objet passé en paramètre est un arbre égal a l'arbre this : meme forme ,et memes données.
11)Écrire une méthode traverse dans la classe Tree qui renvoie la liste des noeuds (List<Node> ) en ordre préfixe.
12)On ajoute le fait que la classe Tree implémente l'interface Iterable<Node>.Comment peut-on utiliser cette propriété?Donner un exemple.
13)Indiquer quelle est la méthode à implémenter pour que la classe Tree respecte l'interface Iterable<Node>.Écrire le code correspondant
14)Dans le but d'écrire une classe PrefixIterator qui parcourt l'arbre dans l'ordre préfixe(ordre identique à celui du toString()),quelle structure de données doit-on utiliser?
15)Donner le code de la classe PrefixIterator.On implémentera la méthode void remove() pour dire qu'elle n'est pas supportée.
ANNEXE
interface java.util.List<E>
-------------------------------------------------------------------
Iterator<E> iterator():Returns an iterator over the elements in this in prper sequence.
ListIterator<E> listIterator(int indexe):Returns a list of the elements in this list (in proper sequence),starting at the specified position in this list.
The specified indexe indicates the first element that would be returned by an initial call to the next mrthod .An initial call to the previous method would return the element with the specified index minus one.In a list of length ,there are n+1 valid index values ,from to n,inclusive.
interface java.util.ListIterator<E>
-----------------------------------------------------------------
public boolean hasNext():Returns true if this list iterator has more elements when traversing the list in the forward direction.
public boolean hasPrevious():Returns true if this list iterator has more elements when traversing the list in the reverse direction.
public E next():Returns the next element in the list.
public E previous():Returns the previous element in the list.
Message édité par Profil supprimé le 13-08-2005 à 11:24:23