Cours sur les arbres 5
14
pages
Breton
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
14
pages
Breton
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
-1- -2-DiversionINF 421 — 05 Luc MarangetOn sait...◮ Les classes sont les ( patrons ) (cf. couture) des objets.◮ Chaque objet poss`ede ses propres composants dynamiques.◮ Tous les objets partagent les mˆeme composants statiques.ArbresSlogan!Ce qui est static est `a la classe, ce qui estdynamique est `a l’objet.Luc.Maranget@inria.frhttp://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/421/-3- -4-Application du sloganImpl´ementation (simplification)class Pair {Deux objets de la mˆeme classe Pair.static int count = 0 ;◮ Ont chacun leur propres champs x et y.int x, y ;◮ Pointent vers le vecteur des variables de la classe Pair.Pair (int x, int y) {this.x = x ; this.y = y ; count++ ;p q}public static void main(String [] arg) {Pair p = new Pair (1, 2), q = new Pair (2, 3) ;System.out.println(count) ;x count x}}y y◮ Quelle est la notation ( compl`ete ) pour count ? Pair.count.◮ Qu’affiche le programme : 2.-5- -6-Cas des m´ethodes Si c’est static, ya pas d’objetLe slogan s’applique encore. Une petite inattention.class Pair {◮ M´ethode static. Il n’y a mˆeme pas besoin de parler d’objet.private int count ;La m´ethode existe, c’est tout. Exemple, Integer.parseInt.int x, y ;Pair (int x, int y) {◮ M´ethode dynamique. Elle est propre a` chaque objet. Exemplethis.x = x ; this.y = y ; count++ ;stack.push(1).}◮ Dans le code d’une m´ethode dynamique, un objet courantstatic int lireCount() {existe, il s’appelle : this ...
Voir
Publié par
Langue
Breton
-4-
Imple´mentation(simplification) Deux objets de l ˆeme classe Pair . a m ◮ Ont chacun leur propres champs x et y . ◮ Pointent vers le vecteur des variables de la classe Pair . p q
x count x y y
Arbres
Slogan! Ce qui est static est`alaclasse,cequiest dynamiqueest`al’objet.
Luc.Maranget@inria.fr http://www.enseignement.polytechnique.fr/profs/ informatique/Luc.Maranget/421/
Luc Maranget
Diversion On sait. . . ◮ Les classes sont les ✭ patrons ✮ (cf. couture) des objets. ◮ Chaqueobjetposs`edesesproprescomposantsdynamiques. ◮ Touslesobjetspartagentlesmeˆmecomposantsstatiques.
-7-
Casdesm´ethodes Le slogan s’applique encore. ◮ Me´thode static .Iln’yamˆemepasbesoindeparlerd’objet. Lam´ethodeexiste,c’esttout.Exemple, Integer . parseInt . ◮ M´ethodedynamique.Elleestpropre`achaqueobjet.Exemple stack . push (1) . ◮ Danslecoded’uneme´thodedynamique,unobjetcourant existe, il s’appelle : this . ◮ Danslecoded’uneme´thodestatiqueonapasacc`esaux champs/m´ethodesdynamiques,cariln’ya pas d’objet .
# javac Pair.java Pair.java : 10 : non-static variable count cannot be referenced from a static context return count ; ^
-6-
-8-
Si c’est static , ya pas d’objet Une petite inattention. class Pair { private int count ; int x , y ; Pair ( int x , int y ) { this . x = x ; this . y = y ; count ++ ; } static int lireCount () { return count ; } } t-cequ¸cacompile?Non!Pourquoi?. Es e Lame´thodestatique lireCount faitre´fe´rence`alavariable non-statique count.
Quelquesexemplesdeme´thodesdynamiques ◮ Codage objet des piles : Stack s1 = new Stack (), s2 = new Stack () ; s1 . push (1) ; s2 . push (2) ; ◮ Sortie standard/d’erreur, System . out / System . err , deux objetsdiffe´rents(rang´esdansdeuxvariablesdeclasses...). System . out . println ( "Je vais dans out" ) ; System . err . println ( "Je vais dans err" ) ; Et si on fait : # java A > bonga ⊲ C¸ a range dans le fichier bonga : ✭ Je vais dans out ✮ . ⊲ Ca affiche : ✭ Je vais dans err ✮ . ¸
-9-
-11-
Un arbre dans la nature
Structurere´cursive( ✭ fractale
✮ )
-10-
-12-
Au final. . .
T → D[-T]+T
-15-
Un autre arbre, plus naturel
T → D[-T]D[++T]T
Les arbres structurants
Proposition
GN GV D N V GN D N
L’ informatique aime les arbres
1--4
-16-
E
1
✭ ´
✮
Ou plus informatiquement. . .
E + E 1 × E E 2 3 + 2 × 3
Surcharge du constructeur Permetdefaireunpeuplusconcis(maisc¸an’irapasloin). Tree ( int val ) { this . val = val ; } new Tree ( new Tree (2), 4, new Tree ( new Tree ( null , 6, new Tree (7)), 8, new Tree (9)))
1
◮ L’arbre (binaire) :
Bon et en Java ? ◮ La liste : 1
-20-
De´finitiondescellulesd’arbre(binaire) class Tree { int val ; Tree left , right ; Tree ( Tree left , int val , Tree right ) { this . left = left ; this . val = val ; this . right = right ; } } Remarquer ◮ Nos arbres ont au plus deux fils. ◮ On retrouve notre dangereux ami, l’arbre vide : null .
7
-21- -22-Arbreetr´ecursivite´Vocabulaire Les arbres sont des structures tr` ´ sives : es recur ◮ L’arbre vide est un arbre. x ◮ Si T 0 et T 1 sont des arbres, alors ( T 0 x T 1 ) est un arbre. x T 0 T 1 ◮ Le ✭ sommet ✮ (ou ✭ nœud ✮ )marque´ x est la racine . ◮ Les arbres T 0 et T 1 sont les sous-arbres . T 0 T 1 ◮ Les racines de T 0 et T 1 sont les fils ( enfants ) de la racine qui Onpeutvoirlesarbrescommesolutionsdecettee´quation.estleur pe`re ( parent ). T = null ⊎ ( T × int × T ) ◮ Si T 0 et T 1 sont l’arbre vide, alors le sommet x est une feuille . Laprogrammationestsyste´matiquementr´ecursive.Enjava,arbre ∼ re´fe´rence,sommet ∼ cellule. -23- -24-Se reperer dans un arbre Hauteur ´ Dans une liste on parlait du k -i`eme´el´ement,dansunarbreonparleLaprofondeurd’unsous-arbreestlalongueurducheminquiy d chemin. ` e mene, 4 4 0 1 2 8 2 8 0 1 6 9 6 9 1 7 7 Parexemplelecheminverslafeuillee´tiquet´ee7est: 1.0.1 . ◮ La hauteur d’un arbre est la profondeur maximale de ses Le chemin vers la racine est : ✭ ✮ (rien ou Λ). sous-arbres Ilest´egalementpratiquederep´ererlessous-arbres(ex. 0.0 ). ◮ C’est aussi la profondeur maximale des feuilles, plus un (arbres Bref,lescheminssonttoutbˆetementdeslistes.vides).
log 2 ( n + 1) ≤ h ≤ n
◮ Arbres avec n maximal :
Soit encore.
Trouver son chemin II Dupointdevueduchemin,oneffectueunparcoursdeliste,d’o`ule code alternatif suivant. static Tree subTree ( Tree t , Chemin c ) { for ( ; c != null ; c = c . next ) { // Traiter d’abord l’erreur i f ( t == null ) { throw new Error () ; } // Ici t n’est pas null i f ( c . val == 0) { t = t . left ; } else i f ( c . val == 1) { t = t . right ; } else { throw new Error () ; } } return t ; } Defait,lare´cursione´taitterminale(cf.amphi02).
-28-
rrro)(};}x:apchoiaslen’yprulIuaetlehaucdlal-C25-htm.+1aMteeHxag(}elsrn0;turne{reun==t(fiuter{)llhtigHeet){etre(T(H1T))tstacinigtT1)=1+max(H(T0).evi)∅(H(H0=0Tocpr..he´e.rrscuc)inf({it,eeemCherTbrT(erTciusee(t==null;}elseifr{terutn=cn=lu)lUCT1C=1.)T10T(C0T=C.0)1Tstaters.entited’lesitsnuimenCnehr{)1rutebusneerTel;}ifse.v(c==al};leest{rhwoenEw(t.right,c.next)iesle};)=lav.c(fwnroth){r(roEreweltf(e.txe)tc,n.retu=0){bTrernsuru,hoctndeheuaetmmets.h≤enantnsoerbrevash2≤nA◮1−l:micnmanig,tefe)tt(l.githht)).right(tHeighalrenroB-62-}};brarunitSourteaunaissantsonchemiLndae´nfitioiindntiucesvesstaclezeriaΛT:(T=0T-2veouTr7--suosnurnocerbra
-29- -30-ArbresstrictementbinairesUneamusantepropri´ete´desarbresbinaires(stricts) Lessommetsontze´rooudeuxfils.Definitionsansl’arbrevide: ´ Unarbrebinairestrictposse`de n + 1 feuilles et n sommets internes. ◮ Une feuille est un arbre. ◮ n = 0, cas de la feuille (cas de base). ◮ Si T 0 et T 1 sont des arbres, alors ( T 0 x T 1 ) est un arbre. ◮ n > 0, soit T = ( T 1 T 2 ) ( n 1 + 1 et n 2 + 1 feuilles chacun), Attention : en programmation null demeure...(pourrepe´rerles ⊲ Nombre de feuilles : ( n 1 + 1) + ( n 2 + 1). feuilles). ⊲ Nombre de sommets internes : n 1 + n 2 + 1, (ceux de T 1 plus class Tree { ceux de T 2 , plus la racine. // Comme avant . Tree ( int x ) { this . val = x ; } // Constructeur des feuilles. boolean isLeaf () { return this . left == null && this . right == null ; } } -31- -32-Parcourir un arbre Parcours en profondeur d’abord En largeur d’abord. Conceptuellement simples, si on veut bien adopter le point de vue re´cursif: 4 ◮ Parcourir sous-arbres par sous-arbre. ◮ Mais encore : 2 8 Pre´fixe: x → T 0 → T 1 . ⊲ → 6 9 ⊲ Infixe : T 0 → x T 1 . ⊲ Postfixe : T 0 → T 1 → x . 7 Iln’yariend’autre`acomprendre(savoir)! Si on parcourt pour afficher, on affichera donc : [4], [2, 8], [6, 9], [7]. C’est conceptuellement assez simple (parcours ✭ pare´tages ✮ de profondeurcroissante),maisunpeud´elicataprogrammer. `
