La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

Cours sur les arbres 5

14 pages
-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 plus Voir moins
-1-INF421052--lpci-3pAdnsutaoi-unco0;t=titantciaPsss{riagolalcnhis.x=x;,inty){tia(rnixtnixty,P;voicatsticblpu;}++tnuoc;y=y.sihtwPaip=nePairrg){[ga]rtniniS(diamlnntri.p);ntou(clleuQ}}onaltsee2),qr(1,Pair=new;)yS2(3,o.tutsmecor.t.unuQchapelergoremma.2:tationcompl`etepuocruotnP?ia
-4-
Imple´mentation(simplication) 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`alobjet.
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.
-5-
-7-
Casdesm´ethodes Le slogan s’applique encore. Me´thode static .Ilnyamˆemepasbesoindeparlerdobjet. Lam´ethodeexiste,cesttout.Exemple, Integer . parseInt . M´ethodedynamique.Elleestpropre`achaqueobjet.Exemple stack . push (1) . Danslecodeduneme´thodedynamique,unobjetcourant existe, il s’appelle : this . Danslecodeduneme´thodestatiqueonapasacc`esaux champs/m´ethodesdynamiques,carilnya 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 objetsdie´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
1--3
-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
-81-17--(eerllunn,6,rTwe(neel,ulnu7,))ll8,n,werTeen(lu,l9,null)))42896unnsuoiqbrFa9--1wen(eerTwenerbranulll,2,(nulTreeenTwer(eenTw,),4
Surcharge du constructeur Permetdefaireunpeuplusconcis(maisc¸anirapasloin). 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´nitiondescellulesdarbre(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,dansunarbreonparleLaprofondeurdunsous-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,oneectueunparcoursdeliste,do`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:apchoiaslenyprulIuaetlehaucdlal-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.entitedlesitsnuimenCnehr{)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.henantnsoerbrevash2nA1l:micnmanig,tefe)tt(l.githht)).right(tHeighalrenroB-62-}};brarunitSourteaunaissantsonchemiLndae´ntioiindntiucesvesstaclezeriaΛT:(T=0T-2veouTr7--suosnurnocerbra
-29- -30-ArbresstrictementbinairesUneamusantepropri´ete´desarbresbinaires(stricts) Lessommetsontze´rooudeuxls.Denitionsanslarbrevide: ´ 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´xe: x T 0 T 1 . 6 9 Infixe : T 0 x T 1 . Postfixe : T 0 T 1 x . 7 Ilnyariendautre`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. `