Lab7 : Les Arbres AVL - Partie B

Objectifs

• Implémenter et appliquer des itérateurs pour une classe générique ArbreAVL.
• Implémenter et appliquer des recherches par bornes.
• Se préparer au TP3.

Lecture préalable

• Section 8.10 des notes de cours.

Tâches

Fichiers du Lab7

Fusionnez votre code obtenu au Lab6 avec le départ du Lab7. Cette tâche consiste principalement à ajouter dans ArbreAVL la classe Iterateur et ses fonctions liées.

wget http://cria2.uqam.ca/INF3105/lab7/lab7.zip
unzip lab7.zip

Itérateurs

Complétez :

1. class Iterateur
2. fonction debut
3. opérateurs []
4. opérateur ++ de Iterateur
5. ...

g++ -o testavl testavl.cpp
./testavl

Construction d'un itérateur suite à une recherche

Complétez :

1. fonction rechercher
2. fonctions rechercherEgalOuPrecedent et rechercherEgalOuSuivant

Bonus: support de la syntaxe des boucles par plage (range-based for loops)

Depuis le standard C++11, on peut utiliser la syntaxe des boucles par plage pour itérer sur un conteneur. La syntaxe suivante:

for(auto& element : conteneur) {
    ...
}

est sémantiquement équivalente à la boucle suivante:

for(auto it = conteneur.begin(); it != conteneur.end(); ++it) {
    auto& element = *it;
    ...
}

Ainsi, pour supporter cette syntaxe, il suffit que la classe sur laquelle on souhaite pouvoir itérer avec cette syntaxe contienne les quatres méthodes suivantes:

Iterateur& Iterateur::operator++();
const T& Iterateur::operator*() const;
Iterateur begin() const;
Iterateur end() const;

Puisque vous avez déjà implémenté les deux premières méthodes, il ne vous reste qu'à ajouter les deux dernières (ou renommer vos méthodes debut() et fin() en begin() et end()).