Comment appliquer le pattern container à d'autres structures récursives (arbres) ?
TreeContent<E> + classe container Tree<E> pour les méthodesAppliquer le pattern container à un arbre binaire pour lui ajouter des méthodes dynamiques.
Définir la paire TreeContent<E> / Tree<E> pour un arbre binaire générique, et implémenter la méthode size().
Appliquer le pattern container à un arbre binaire pour lui ajouter des méthodes dynamiques.
Le même schéma s'applique : TreeContent<E> stocke la structure récursive de l'arbre (valeur, gauche, droit), et Tree<E> est le container public portant les méthodes dynamiques.
class TreeContent<E> avec les champs E value, TreeContent<E> left, TreeContent<E> right et le constructeur.class Tree<E> avec un champ TreeContent<E> content ; content == null = arbre vide.size(), depth(), value()…) sur le container en testant this.content == null pour le cas arbre vide.Définir la paire TreeContent<E> / Tree<E> pour un arbre binaire générique, et implémenter la méthode size().
class TreeContent<E> avec les champs E value, TreeContent<E> left, TreeContent<E> right et le constructeur.Définir TreeContent<E>, la classe récursive interne de stockage :
class TreeContent<E> {
E value;
TreeContent<E> left;
TreeContent<E> right;
TreeContent(E v, TreeContent<E> l, TreeContent<E> r) {
value = v;
left = l;
right = r;
}
}
class Tree<E> avec un champ TreeContent<E> content ; content == null = arbre vide.Définir le container Tree<E> avec son champ content et ses constructeurs :
class Tree<E> {
TreeContent<E> content;
Tree() { content = null; } // arbre vide
Tree(E v, Tree<E> l, Tree<E> r) {
content = new TreeContent<E>(v, l.content, r.content);
}
Tree(TreeContent<E> c) { content = c; } // usage interne
}
size(), depth(), value()…) sur le container en testant this.content == null pour le cas arbre vide.Implémenter size() sur le container en testant this.content == null pour l'arbre vide :
int size() {
if (this.content == null) return 0; // arbre vide
Tree<E> left = new Tree<E>(content.left);
Tree<E> right = new Tree<E>(content.right);
return 1 + left.size() + right.size();
}
// Test : arbre vide -> 0, feuille -> 1, arbre [1, [2], [3]] -> 3
Le pattern container s'applique aux arbres exactement comme aux listes : TreeContent<E> stocke, Tree<E> porte les méthodes, et this.content == null détecte l'arbre vide.
Implémenter la méthode depth() (profondeur maximale) sur le container Tree<E>.
Implémenter value() sur Tree<E> et montrer que le même pattern container s'applique à un arbre n-aire.
Crée ton compte pour accéder à la fiche et aux exercices