UTBM theorie de la programmation tda et structures de donnees 2005 gi

UTBM le 16 janvier 2006 Final – LO42 Les documents sont autorisés (La copie ou les idées du voisin non). Le barème est indicatif. Le soin donné à la rédaction sera évalué. Toute réponse devra être claire et justifiée (toute ambiguïté sera mal interprétée). L’élégance de la solution sera jugée. Sauf indication contraire, dans le cas d’algorithmes, les réponses doivent être rédigées en pseudo code. L’exercice 3 est à faire sur une feuille séparée 1) La multiplication des pins (5) (en Java) Voici une classe java : public class ArbreBinaire { public ArbreBinaire droit() { return d; } Object r; // la racine de l'arbre public ArbreBinaire setDroit(ArbreBinaire a) { ArbreBinaire g, d; // les sous-arbres return (d = a); } protected ArbreBinaire(Object r, ArbreBinaire g, ArbreBinaire d) { // construction de l'arbre : a = f.cons(r,d) this.r = r; public ArbreBinaire cons(Object r, ArbreBinaire d) { this.g = g; return new ArbreBinaire (r,this, d); this.d = d; } } protected ArbreBinaire(Object r) { this(r,creer,creer); } /** Le seul moyen d'initialiser un nouvel arbre binaire : protected ArbreBinaire() { this(null,creer,creer); } * ArbreBinaire a = ArbreBinaire.creer; */ public Object racine() { return r; } static public final ArbreBinaire creer = new ArbreBinaire (); public Object setRacine(Object r) { return (this.r = r) ; } public boolean estVide() { public ArbreBinaire gauche() { return g; } ...