Cours sur les arbres 5

Description

-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’[e-mail]://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 ...

Sujets

• informatique
• ordinateur

Informations

• Publié par: Mafen
• Nombre de lectures: 62
• Langue: Breton

Extrait

-1- INF421—05 2-- lpci -3 pAdnsutaoi - unco0;t=titantci aPss s {ri agol alc n his.x=x; ,inty){ t ia(rnixt nixty, P ; voicatsticblpu ; } ++tnuoc;y=y.siht wPaip=nePair rg){[ga]rtniniS(diam lnntri.p);ntou(c lleuQ◮ } } onaltsee 2),qr(1,Pair=new;) yS 2(3, o.tutsme cor.t.un u’◮Qchaffipelergoremma.2: tation✭compl`etep✮uocruotnP?ia

-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.

[e-mail] 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 .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

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,))ll 8 , n , werTeen(lu,l9,null))) 4 28 96 unnsuoiqbrFa 9--1 wen (eerTwen erbra nulll,2,(nulTree enTw er(eenTw ,) ,4

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,dansunarbreonparle Laprofondeurd’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’yp ru lI uaetlehaucdlal - C 25- htm.+1aMteeHxag( }els rn0; turn e{ re un==t(fi uter {)ll htigHeet){etre(T (H 1 T)) tstacinigt T 1 )=1+max(H(T 0 ) .evi )∅(H (H 0=  0 T ocpr..he´e.rrscu c)in f( { i t,eeemCherTbrT(erTciusee (t==null ; }elseif r { terutn =cn=lu)l  U CT 1 C=1.)T 1  0 T(C 0 T=C.0) 1 T stat ers.entited’lesitsnuimenCneh r {)1 rutebusneerT el ; }ifse.v(c==al } ; lees t { rhwoenEw (t.right,c.next) iesle} ;) =lav.c(f wnroth ){ r(roErew eltf(e.txe)tc,n.retu =0){ bTrernsu ru,hoctndeheuaetmmets. h≤ enantnso erbrevas h 2≤n A◮ 1− l:micnmani g,tefe)tt(l.githht)).right(tHeig halrenroB -62- } } ; brarunitSo urteau naissantsonchemi L n dae´nfitioiindntiucesvesstaclezeria ΛT : (T= 0 T -2 veouTr 7- -suosnurnocerbra

-29- -30- Arbresstrictementbinaires Uneamusantepropri´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. `