[PDF] Parcours d’un arbre binaire - Claude Bernard University Lyon 1

Ch1 - Xavier Viennot

Un sommet x de I'arbre binaire B est appelé sommet double (resp simple , resp feuille ) ssi x a deux fils, (resp un seul ms, resp pas de fils) Les sommets simples se classifient en sommets simples à gauche (resp simples à droite ) selon que l'unique fils est fils à gauche (resp fils à dmite) Exemple: fg (3) = 6 fils gauche ms droit

TD 6 Arbres binaires 1 Exercices

Donner l’algorithme r´ecursif de parcours g´en´eralis´e d’un Arbre binaire (les proc´edures de traitement sont nomm´ees traitement1, traitement2 et traitement3) Chaque sommet est rencontr´e trois fois (`a la descente, lors de la remont´ee du fils gauche puis du fils droit : faire un

Parcours d’arbres

Parcours symétrique (arbre binaire) \ - (b\c)] partir d’un sommet s d’un graphe orienté, les sommets visités représentent l’ensemble des

Parcours d’un arbre binaire - Claude Bernard University Lyon 1

Parcours d’un arbre binaire Un arbre binaire est un arbre avec racine dans lequel tout noeud a au plus deux fils : un éventuel fils gauche et un éventuel fils droit On illustrera avec l’arbre binaire suivant : r a c h d i j ‘ b e k f 1 Balade autour de l’arbre

Algorithmique avancée - Arbres binaires de recherche

Arbre binaire Définitions Un arbre d’arité 2 est un arbre binaire Il a au maximum deux fils, un fils gauche et un fils droit Un arbre binaire est dit pur si chacun des nœuds a soit exactement 2 fils, soit aucun Un arbre binaire de recherche (ABR) est un type de données abstrait constitué d’un couple (clé,valeur)

Cours 7: Arbres de recherche Tas - LIX

Arbre binaire de recherche Un arbre binaire de recherche est un arbre binaire, dans lequel chaque sommet est ´etiquet´e par un couple (k,D), avec la propri´et´e suivante: I tous les sommets du sous-arbre • gauche ont une cl´e inf´erieure `a k • droit ont une cl´e sup´erieure `a k Exemple: 7 3 1 4 5 9 8

Examen n 2 - Université du Luxembourg

Un arbre est constitu´e d’un ensemble de noeuds auquels sont associ´ees des valeurs (de type T) Un arbre binaire est d´efini r´ecursivement de la mani`ere suivante : un arbre binaire est compos´e — soit d’un seul sommet appel´e racine, 2

TD : Arbres Binaires de Recherche (ABR)

Question 4 Donner l’algorithme qui r ealise une rotation droite en un sommet yd’un arbre donn e Exercice 4 (Arbres Rouge et Noir : algorithmes) La strat egie pour r ealiser l’insertion dans un A B R propos ee dans [1] consiste a un ins erer un noeud dans un arbre binaire de recherche et a lui donner la couleur rouge Si le p ere du

Arbres binaires de recherche - pagepersolifuniv-mrsfr

Parcours d’un arbre binaire Le parcours le plus simple a programmer est le parcours dit en profondeur d’abord Son principe est simple : pour parcourir un arbre non vide a, on parcourt r´ecursivement son sous-arbre gauche, puis son sous-arbre droit, la racine de l’arbre pouvant ˆetre trait´ee au d´ebut, entre les deux parcours ou a

[PDF] arbre binaire java

[PDF] retour ? l'unité proportionnalité

[PDF] le timbre d'un son

[PDF] psychologie criminelle cours pdf

[PDF] passage ? l'acte psychologie

[PDF] cours de criminologie générale pdf

[PDF] livre criminologie pdf

[PDF] tétraèdre régulier propriétés

[PDF] passage ? l'acte

[PDF] tétraèdre propriétés

[PDF] grille d'estimation de la dangerosité d'un passage ? l'acte suicidaire pondération

[PDF] intervenir auprès de la personne suicidaire ? l'aide de bonnes pratiques

[PDF] grille estimation dangerosité suicidaire

[PDF] grille d'évaluation de l'urgence suicidaire

[PDF] rapport d'intervention auprès de la personne suicidaire

IREM DE LYON

Parcours d"un arbre binaire

Un arbre binaire est un arbre avec racine dans lequel tout noeud a au plus deux fils : un éventuel fils

gauche et un éventuel fils droit.

On illustrera avec l"arbre binaire suivant :r

a c hd ij `b e kf

1 Balade autour de l"arbre

On se balade autour de l"arbre en suivant les pointillés dans l"ordre des numéros indiqués :r

a c hd ij `b e kf1 2 3456
7 89

101112131415

16

171819202122

1

IREM DE LYON

1.1 Première définition des trois parcours

A partir de ce contour, on définit trois parcours des sommets de l"arbre : 1.

l "ordrep réfixe: on li stech aqueso mmetl apr emièrefois qu "onle r encontredan sla b alade.C eq ui

donne ici : ... 2.

l "ordrepost fixe: on liste c haquesomm etla der nièrefois q u"onle r encontre.C eq uidonn ei ci: . ..

3.

l "ordrein fixe: on li stec haquesommet ay antu nfils gauche l asecon defois qu "onl ev oitet cha que

sommet sans fils gauche la première fois qu"on le voit. Ce qui donne ici : ...

Une résolution

1. or drepréfixe : r,a,c,h,d,i,j,`,b,e,k,f. 2. or drepost fixe: h,c,i,`,j,d,a,k,e,f,b,r. 3. or dreinfix e: c,h,a,i,d,`,j,r,k,e,b,f.1.2 Seconde définition des trois parcours Dans la balade schématisée plus haut, on ajoute les fils fantômes manquants :r a c hd ij `b e kf

On peut ainsi considérer qu"on passe une fois à gauche de chaque noeud (en descendant), une fois en-

dessous de chaque noeud, une fois à droite de chaque noeud (en remontant). soit lor squ"onp asseà leu rga uche, soit lor squ"onp asseà leu rdr oite, soit lor squ"onp asseen-dessous .

Une résolution

1.

A g auche: préfix e.2

IREM DE LYON

2.

A d roite: post fixe.

3.

E n-dessous: i nfixe.2 Algorithmes récursifs

Pour chacun des parcours définis ci-dessus (postfixe, infixe, préfixe), définir récursivement le parcours.

Une résolution

1.

P arcoursp réfixe.Pseudo-code

ParcoursPréfixe (Arbre binaire T de racine r )

Afficher clef [ r ]

ParcoursPréfixe (Arbre de racine fils_gauche [ r ]) ParcoursPréfixe (Arbre de racine fils_droit [ r ])2.P arcoursp ostfixe.

Pseudo-code

ParcoursPostfixe (Arbre binaire T de racine r )

ParcoursPostfixe (Arbre de racine fils_gauche [ r ]) ParcoursPostfixe (Arbre de racine fils_droit [ r ])

Afficher clef [ r ]3.P arcoursin fixe.

Pseudo-code

ParcoursInfixe (Arbre binaire T de racine r )

ParcoursInfixe (Arbre de racine fils_gauche [ r ])

Afficher clef [ r ]

ParcoursInfixe (Arbre de racine fils_droit [ r ])3 Représentation en machine

Chaque noeud de l"arbre T est representé par un objet ayant un champ clef (des valeurs à trier par

exemple), un champ père, un champ fils_gauche, un champ fils_droit (stockent des pointeurs). Lorsque père[x]=NIL,xest la racine de l"arbre. Lorsquexn"a pas de fils gauche, fils_gauche[x]=NIL

(idem pour fils_droit). La racine de l"arbreTest pointée par l"attribut racine[T]. Lorsque racine[T]=NIL,

l"arbre est vide.3

IREM DE LYON

4 Complexité d"un parcours infixe

Vérifier qu"avecnnoeuds, le parcours infixePseudo-code

Parcours_Infixe (arbre binaire T de racine x)

Six distinct de NIL*****temps constant T(0)=c pour un sous¡arbre vide alors Parcours_Infixe ( arbre de racine fils_gauche [x]) *****temps T(k)

Afficher clef [x]

*****temps constant d

Parcours_Infixe ( arbre de racine fils_droit [x])

*****temps T(n¡k¡1)

FinSiprend un temps en£(n) (établir avec les notations suggérées ci-dessus :T(n)AE(cÅd)nÅc)

Une résolution

Amorce :T(0)AEcAE(cÅd)£0Åc.

Hérédité :

T(n)AET(k)ÅT(n¡k¡1)Åd

AE(cÅd)nÅc¡(cÅd)ÅcÅd

AE(cÅd)nÅc

5 La notation polonaise inverse

Écrire les sommets de l"arbre ci-dessous pour chacun des ordres postfixe, préfixe, infixe :¥

ab¡ cdÅ ef

Pour le parcours infixe, on ajoute la convention suivante : on ajoute une parenthèse ouvrante à chaque

fois qu"on entre dans un sous-arbre et on ajoute une parenthèse fermante lorsqu"on quitte ce sous-

arbre.4

IREM DE LYON

Une résolution

1. P réfixe(n otationpolo naise): ¥,£,Å,a,b,¡,c,d,Å,e,f. 2. P ostfixe(p olonaisein verse): a,b,Å,c,d,¡,£,e,f,Å,¥. 3.

I nfixe: a,Å,b,£,c,¡,d,¥,e,Å,f.

Avec un ajout de parenthèses (ouvrante en rencontrant le noeud racine du sous arbre pour la pre-

mière fois et fermante lorsqu"on le rencontre pour la dernière fois, avec exception sur les sous-

arbres constitués d"une feuille) :¡(aÅb)£(c¡d)¢¥(eÅf).

L"infixe nécessite cette convention pour lever les ambiguïtés, les deux autres non. La préfixe consiste à

voir les opérateurs comme des fonctions de deux variables : [Å(a,b),¡(c,d)],Å(e,f)´ Idem avec la postfixe mais avec la fonction écrite sur la droite.6 Le tri du bijoutier

On dispose d"une liste de nombres. Par exemple, la liste 7, 9, 3, 5, 4, 1, 8. On associe à chaque élémentn

de la liste un noeudv(initialisation : père[v]=NIL, fils_gauche[v]=NIL, fils_droit[v]=NIL, clef[v]=n).Pseudo-code

Arbre_Insérer(Arbre T, noeud z)

y:=NIL x:=racine [T]

TantQuex distinct de NIL faire

y:=x

Siclef [z] alorsx:= fils_gauche [x] sinonx:= fils_droit [x] FinSi

FinTantQue

père[z]:=y

Siy=NIL

alorsracine [T]:=z sinon

Siclef [z] alorsfils_gauche [y]:=z sinonfils_droit [y]:=z FinSi

FinSi5

IREM DE LYON

1.

D resserl "arbreobt enuen app liquantl "algorithmeArbr e_Inséreraux élément sde la l iste(dan s

l"ordre de la liste) en partant d"un arbre vide pour le premier élément, chaque appel à l"algorithme

modifiant l"arbre. 2. L "undes pa rcourspost fixe,infi xe,préfixe de la liste t riela liste .Lequ el? 3. D ansl acon structionde l "arbrepou ru neli sted ennombres, quel est le nombre de comparaisons effectuées dans le pire des cas? 4.

Q uele stl en ombrede compa raisonse ffectuéessi l "arbrefi nalest un arbr ebin airecomplet (arbr e

binaire dans lequel tout noeud autre qu"une feuille a deux fils et dans lequel les feuilles sont tous

des noeuds de même profondeur).

Une résolution

1.

L "arbreobt enu: 7

3 15 49
8 2.

Le p arcoursin fixetr iel ali ste.Les é lémentsde g auchesont e ne ffetpar const ructionp luspetit s

qu"un noeud et sont affichés avant le noeud dans l"ordre infixe et les éléments de droite qui sont,

par construction, plus grands sont affichés dans l"ordre infixe après le noeud. Par "récurrence", on

a donc un affichage des éléments de la liste dans l"ordre. On peut donner une version graphique de ce parcours en projetant verticalement les noeuds sur une droite horizontale (à dessiner sous l"arbre). 3.

Le p iredes cas corr espondaux cas où la li stee sttr iée(or drec roissantou décr oissant).Le nombr e

de comparaisons à effectuer est alors de 1Å2Å¢¢¢Å(n¡1)AE12 n(n¡1). 4. P ourajou teru nn oeuda univ eaude p rofondeurp(la racine étant au niveau de profondeur 0), on effectuepcomparaisons. Si la profondeur esth, on aura effectué une comparaison pour chacun des deux noeuds de profondeur 1 (2£1), deux comparaisons pour chacun des 22noeuds de pro- fondeur 2 ( total 2

1Å2£22), tros comparaisons pour chacun des 23noeuds de profondeur 3 (total

2

1Å2£22Å3£23) ...

Le nombre de comparaisons pour une profondeurhest (preuve facile par récurrence) : h X jAE1j£2jAE(h¡1)£2hÅ1Å26

IREM DE LYON

Avecnnoeuds (c"est à dirennombres à trier), on a 1Å2Å22Å¢¢¢Å2hAE2hÅ1¡1 et

h X On a donc un cas optimal enO(nlog(n)) et on peut montrer (comme pour le quick sort) que la hauteur moyenne d"un arbre binaire de recherche construit aléatoirement à partir denclefs

estO(log(n)) (référence : introduction à l"algorithmique, Cormen, Leiserson,Rivest, Stein, éditions

Dunod, 2002, page 258, paragraphe 12.4).

Les caractéristiques de temps sont les mêmes que pour le quick sort, mais avec un avantage du on crée un arbre de recherche pour le tri du bijoutier).7 Références 1.

I ntroductionà l "algorithmique.A uteurs: C ormen,Le iserson,Riv est,S tein.E ditionf rançaise: D u-

nod 2002.

Plus de 1100 pages sur les algorithmes et les structures de référence. Le chapitre 12 concerne les

arbres binaires de recherche. 2. U nar ticlede J ean-ClaudeO riolsur le site de l "apmepa vecu npas sagesur l et ridu b ijoutier: 3.

Le cou rsde Pierr eA udibert(P aris8 )en l igne:

quotesdbs_dbs44.pdfusesText_44