[PDF] Algorithmique et Structures de données

Donner des exemples d'arbres binaires complets 2 Ecrire une fonction qui teste si un arbre binaire est complet Exercice 5 6 Arbre binaire parfait On

[PDF] Cours 5 : Arbres Binaires Extensions : AVL - LIMSI

1 Arbres binaires complets 2 Arbres AVL Il n'y a qu'un arbre binaire plein d' une hauteur donnée (`a Définition d'un Arbre Binaire complet Définition :

[PDF] Les arbres - UQAC

Arbre complet: Un arbre est complet si toutes ses feuilles sont sur le même Pour les arbres binaires, les deux enfants seront représentés par les champs

[PDF] Arbres binaires de recherche - CNU 27 Marseille

Arbres binaires : hauteur, nombre de noeuds et nombre de feuilles Un arbre binaire est complet si toutes ses branches ont la même longueur et tous ses noeuds

[PDF] Parcours dun arbre binaire

Quel est le nombre de comparaisons effectuées si l'arbre final est un arbre binaire complet (arbre binaire dans lequel tout nœud autre qu'une feuille a deux fils et

[PDF] arbres binaires - Ensiwiki

Arbres binaires particuliers Localement complet les nœuds internes ont 2 fils nb feuilles = nb nœuds + 1 Complet localement complet et branches de même

[PDF] INAL_4_Les arbres - LIP6

Arbre binaire complet : 1 nœud à la hauteur 0 2 nœuds à la hauteur 1 4 nœuds à la hauteur 2 Nombre total de nœuds : 1 + 2 + 22 + + 2h = 2h+1 - 1

[PDF] Algorithmique Les arbres

nœud = question, feuille = réponse ; branche gauche étiquetée par FAUX, branche droite par VRAI Recherche : par arbres binaires de recherche Files de priorité

[PDF] TD 7 : Algorithmique fonctionnelle Arbres binaires - grug

Question 3 : Soit A un arbre binaire complet de hauteur H Quel est le nombre de feuilles de A ? Prouvez votre formule par récurrence 3 Page 4

[PDF] Arbres

Un arbre binaire complet de hauteur h est formé par un arbre parfait de hauteur h -1 et par une ou plusieurs feuilles au niveau h De plus les feuilles du dernier

[PDF] dénombrement cours

[PDF] arbre de probabilité pile ou face

[PDF] arbre de probabilité seconde

[PDF] arbre probabilité conditionnelle

[PDF] arbre de décision exercices corrigés

[PDF] arbre de décision data mining

[PDF] cours arbre de décision

[PDF] classification par arbre de décision

[PDF] arbre de décision exemple

[PDF] arbre de décision cart

[PDF] construire un arbre de décision

[PDF] arbre de décision définition

[PDF] dénombrement cours 1ere s

[PDF] apollon et daphné résumé

[PDF] apollon et daphné leur histoire

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

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