[PDF] [PDF] Algorithmique et Structures de données - LaBRI

[PDF] Parcours dun arbre binaire

Un arbre binaire est un arbre avec racine dans lequel tout noeud a au plus deux 3 l'ordre infixe : on liste chaque sommet ayant un fils gauche la seconde fois 

[PDF] stage graphes

Dans un arbre binaire presque complet ayant n sommets, montrer que le nombre maximal de descendants d'un fils de la racine est 2n/3 On pourra commencer 

[PDF] Arbres binaires de recherche - CNU 27 Marseille

Arbres binaires : hauteur, nombre de noeuds et nombre de feuilles cas d'arbre non planté, puisqu'il n'y a pas de sommet particulier qui joue le rôle de racine

[PDF] Algorithmique et Structures de données - LaBRI

On appelle arbre binaire complet un arbre binaire tel que chaque sommet interne a exac- tement 2 fils 1 Donner des exemples d'arbres binaires complets 2

[PDF] TP 8 : Arbres binaires de recherche - Cedric-Cnam

d'un arbre binaire de manière à lire la structure de l'arbre si le noeud à enlever a deux fils, on le remplace par le sommet de plus petite valeur dans le

[PDF] Arbres binaires de recherche : propriétés combinatoires - Numdam

étiquettes des sommets d'un arbre binaire décroissant pris en ordre symétrique, (dit aussi sommet interne) appelé la racine de l'arbre, g (respectivement d)

[PDF] Les arbres binaires - Laboratoire de Recherche en Informatique

Un arbre binaire peut être vide • Un arbre binaire possède un nœud (étiqueté ou pas) racine feuilles sommets − 4 + 3 * 2 5 2013-2014 Algorithmique 8 

[PDF] Graphes, Arbres, Arbres Binaires - Inria

Si, de plus, n > 2 et {vn,v1} ∈ E, alors (v1,··· ,vn) est un cycle Le graphe G est connexe si (et seulement si), pour tous sommets u,v ∈ V, il existe un chemin entre 

[PDF] TDA Arbre Binaire

27 fév 2010 · (sous-arbres) Un sommet de l'arbre est la racine d'un sous-arbre Dans un arbre binaire tout noeud a au plus deux fils Un arbre binaire 

[PDF] arbre binaire java

[PDF] retour ? l'unité proportionnalité

[PDF] le timbre d'un son

[PDF] le passage ? l’acte criminel

[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

Universit´eBordeaux1LicenceInformatiq ue2013-2014

Algorithmiqueet Structuresdedonn´ ees

Feuille5:Arbresbin air es

Onco nsid`erelet ypeabs traitarbreBinaired'objetd´efiniencours.

Pourrappel voirannexeA.

Exercice5.1Impl´ementationdutypeab straitarbr eBinaire (rappelducoursenAnn exeB) -Soitl'arbredelaFig.1(a).Sonimpl´ementationdyna miqueestillustr´eesur laFig.1(b). Onaj outeunefeuilleaud ernierniv eau.Dessinerlanouvel lestru cture. 3 54
1 2 ref A: arbreBinaire 23
5 1 4 (a)(b)

Figure1-Arbrebinairecomplet

-Compl´eterl'impl ´ementationvueencou rsparl esprimitiv es: filsDroit,pere,ajouterFilsDroit, supprimerFilsDroit.

Exercice5.2Parcours

Soitl'arbre binairedontlesfeuille ssont´etiquet´eesav eclesnombresna ture lsillustr´esurFig.2.

4 6 2 1 3 5 8 9 7

Figure2-Arbrebinaire

1.Donn erlesmotscorres pondant sresp.`asonparcourspr´efixe,infixeet su!xe.

2.Existe-t-ilu nar brebina ire`a8sommetsdontlemotpr´efixeest12345678etle mot

su xeest (a)53247681? (b)43527861? Onsu pposeraquelesfeuillessont´ etiquet´eesav eclesnombresna turels n,n!8.

3.Don nerleprinciped' unalgorit hmepourreconstruireunarbre binaire`apartirdeses

motsinfixe,pr´efixeetsu !xe.

Exercice5.3Parcourshi´erarchique

Soitletable aud'ent iersTab={0,2, 3,4,6, 7,9,10, 12,13,14, 16,20} etla fon ctionremplirTableauArbrevueen cours(annexe C). Dessinerl'arbrebin aireproduitparl'appel `aremplirTableauArbre(Tab).

Exercice5.4Parcoursenprofondeur

Enu tilisantl'algorithmedep arcoursenprofonde ur:

1.´ecrireunefonc tionquicomptelen ombredefeuilles dansun arbrebina ire.

2.´ecrireunefoncti onquicalcul elahauteurd'unarbrebi naire.

3.´ecrireunefoncti onquiretou rneleminimumdesvaleurs contenuesdan sunarbrebinaire.

4.´ecrireunefoncti onquiteste siun´el´ementappart ient`aunarbrebinaire.

endenumerate

Exercice5.5Arbrebinairec omplet

Onap pellearbrebinairecomplet unar brebinairete lquechaquesommetinterne aexac- tement2fils.

1.Don nerdesexemplesd 'arbresb inairescomplets.

2.E crireunefonctionquit estesiunar brebinaireestcomple t.

Exercice5.6 Arbrebinairep arfait

Onap pellearbrebinaireparfait unar brebinairecomple tdanslequeltoutesl esfeuilles sont`alamˆemehaut eurdansl'arbre.

1.Don nerdesexemplesd 'arbresbi nairesparfaits.

2.Ecr ireunefonctionquites tesiunarbr ebinaireestparfait.

Exercice5.7Arbrebinaireq uasi-parfait

Onap pellearbrebinairequasi-parfait unarbre binai reparfait´eventuellementgrignot´e d'un´etageenb as` adroite.

1.Don nerdesexemples d'arbresbi nairesquasi-parfaits.

2.Ec rireunefonctionquite stesiunar brebinaireestquasi-p arfait.

Exercice5.8Evaluationd'expressionsarith m´etiques Onsu pposedonn´eunarbrebinairerepr´esentantuneexpressi onarithm´etiqueconten antdes entiersetdesop´ erateursbinaires+et*.Sil'expressionestbienform´ee(corr ecte)alors 2 l'arbrebinaireestcomp let.Chaquefeuilledecetarbre contientdon cunent ieretchaque noeudinterne unop´erateur(l'undess ymboles+ou*). Onad optecommeconventio nquelesymbole+estcod´ epar-1et*par-2. Ecrireunefonctio nvaleurExpression(valA: arbreBinaire)qui´evaluelavaleur del' expressionrepr´esent´eepa runarbreb inaire sil'arbreestcomp letsinonrenvoieNIL,en visitantuneetuneseulefoist ous lesnoe udsdel 'arbre(unseu lparcoursdel'arbre ).

Probl`emer´ ecurrent(notrefild'ariane )

Exercice5.9 Gestiond'unepiste d'atterrissagedesa vions

Unav ionestunenregist rementcont enant:

-l'indicatif(6caract`eres) -ladestination(30caract`eres) -l'autonomier´esiduelledecarburantcompt ´eeenh eures devol(entier) -deuxbool´eensind iquants'ilyaunpirate`abordets'ilyalefeu.

1.D´ efinirlesstructu resdedo nn´eesn´ ecessaires.

2.Ec rirelafonctionPriorit´eainsiquelagest ioncompl`etede lapiste.

3.En visagerlecasdesuppressi ond'un´ el´ementquelcon quedelafilelorsquelepirateamis

samena ceded´etournement`aex´ecution. Quellessontlesnoti onsquevousvene zdevoirqui peuventpermettred'amorce rlefild' ariane? 3

AnnexeATypeabstra itarbreBinaire

arbreBinaire=curseur; sommet=curseur; -Cr´eation -Acc`es fonctiongetValeur(valS:sommet):objet; fonctionfilsGauche(valS:sommet):sommet; fonctionfilsDroit(val S:sommet):sommet; fonctionpere(valS:sommet):sommet; -Modification fonctionsetValeur(refS:sommet, valx:objet):vide; fonctionajouterFilsGauche(refS:sommet, valx:objet):vide; fonctionajouterFilsDroit(refS:sommet, x:objet):vide; fonctiondetruireSommet(ref S:sommet):vide; AnnexeB Impl´ementationdutyp eabstraitarbreBinaire cellule=structure info:objet; gauche:sommet; droit:sommet; pere:sommet; finstructure sommet=^cellule; 4 AnnexeCConstructiond'unarbrebinaire`apar tird'untableau fonctionremplirTableauArbre(refT:tableau[1..N] d'entier): arbreBinaired'entier; varA:arbreBinaired'entier; varF:file desommet; vars:sommet; vari:entier; debut creerFile(F);

A=creerArbreBinaire(T[1]);

enfiler(F,A); tmp=2; tantque2*tmp-1<= Nfaire pouri=tmp a2*tmp-1par pasde2 faire s=getValeur(F); defiler(F); ajouterFilsGauche(s,T[i]); enfiler(F,filsGauche(s)); ajouterFilsDroit(s,T[i+1]); enfiler(F,filsDroit(s)); finpour; tmp=tmp*2; fintantque pouri=tmpa N-1parpas de2faire s=getValeur(F); defiler(F); ajouterFilsGauche(s,T[i]); ajouterFilsDroit(s,T[i+1]); finpour; siNmod 2==0 alors ajouterFilsGauche(getValeur(F),T[N]) finsi detruireFile(F); retourner(A); fin 5quotesdbs_dbs44.pdfusesText_44