Arbre

Itérateur sur les arbres binaires avec une classe externe

La classe Arbre implémente des arbres binaires non modifiables, dans un style "fonctionnel". La classe ArbreIteration fournit un itérateur sur ces arbres en faisant un parcours en profondeur (DFS) avec un traitement postfixe : un noeud est retourné quand tous les noeuds de ses sous-arbres gauche puis droit ont déjà été retournés. La classe Test donne un exemple d'utilisation.
L'algorithme utilisé est le suivant :

soit a un noeud,

premier(a) le premier noeud à traiter dans un arbre de racine a
suivant(a) le noeud à traiter après avoir traité le noeud a
gauche(a) le fils gauche de a
droit(a) son fils droit.

premier(a) =

si gauche(a) ≠ null alors premier(gauche(a)

sinon si droit(a) ≠ null alors premier(droit(a))

sinon a

suivant (a) =

premier(droit(pere(a))) si pere(a) ≠ null et gauche(pere(a)) = a et droit(pere(a)) ≠ null

pere(a) sinon

Itérateur sur les arbres binaires avec une classe interne anonyme

Dans cette version, l'itérateur est créé à l'aide d'une classe interne anonyme dans la classe Arbre. La classe ArbreIteration n'existe plus et la classe Test a été légèrement modifiée.

Itérateur interne sur les arbres binaires

Cette version donne un exemple d'itération interne grâce à l'ajout de la méthode

appliquer(Fonction<T>
f)

à la classe Arbre. Une interface Fonction pour représenter le traitement à appliquer est donc nécessaire. La classe Test a été modifiée en conséquence. A noter que la méthode f(T t) dans l'interface Fonction renvoie un booléen. Cela permet d'arrêter l'itération en renvoyant false.

Itérateur protégé sur les arbres binaires

Dans cette version, les arbres sont modifiables. L'itération est protégée de façon à ce qu'il ne soit pas possible d'élaguer un arbre alors qu'une itération est en cours. La classe Arbre a donc été modifée, ainsi que la classe Test.