Algorithmique 1

Publié par

Licence, Supérieur, Licence (bac+3)
  • cours - matière potentielle : en annexe b
  • cours - matière potentielle : par les primitives
Universite Bordeaux 1 Licence Informatique 2011-2012 Algorithmique 1 Feuille 5 : Arbres binaires On considere le type abstrait arbreBinaire d'objet defini en cours. Pour rappel voir annexe A. Exercice 5.1 Implementation du type abstrait arbreBinaire (rappel du cours en Annexe B) – Soit l'arbre de la Fig.1(a). Son implementation dynamique est illustree sur la Fig.1(b). On ajoute une feuille au dernier niveau.
  • arbrebinaire
  • autonomie residuelle de carburant comptee en heures de vol
  • arbre binaire
  • arbres binaires
  • nouvelle structure
  • nouvelles structures
  • entiers
  • entier
  • entière
Publié le : mardi 27 mars 2012
Lecture(s) : 46
Source : labri.fr
Nombre de pages : 5
Voir plus Voir moins
Universit´eBordeaux1LicenceInformatique20112012 Algorithmique 1 Feuille 5 : Arbres binaires Onconside`reletypeabstraitarbreBinaire d’objeteicnuosr.de´nPour rappel voir annexe A.
Exercice 5.1iaatsbrtpyaedntuireBinarbrentmeioatIm´epl (rappel du cours en Annexe B) SoitlarbredelaFig.1(a).Sonimpl´ementationdynamiqueestillustr´eesur la Fig.1(b). On ajoute une feuille au dernier niveau. Dessiner la nouvelle structure. ref A: arbreBinaire 1 1q 2 3 2q q3 4 5 4q q5q q (a) (b) Figure1 – Arbre binaire complet Comple´terlimpl´ementationvueencoursparlesprimitives: filsDroit, pere, ajouterFilsDroit, supprimerFilsDroit. ´ – Ecrireune fonctionmeme_squelettequi teste si deux arbres binaires sont 1 semblablesa`lavaleurpre`sdesvaleurscontenuesdanslessommets.
Exercice 5.2Parcours Soitlarbrebinairedontlesfeuillessonte´tiquete´esaveclesnombresnaturels illustre´surFig.2. 1.Donnerlesmotscorrespondantsresp.a`sonparcourspre´xe,inxeet suffixe. 2.Existetilunarbrebinaire`a8sommetsdontlemotpre´xeest12345678 et le mot suffixe est (a) 53247681? (b) 43527861? Onsupposeraquelesfeuillessonte´tiquete´esaveclesnombresnaturelsn, n8. 1.Onutiliseralesprimitivesdonn´eesenAnnexeB
1 2 3
4 6
7
5
9
Figure2 – Arbre binaire
8
3.Donnerleprincipedunalgorithmepourreconstruireunarbrebinairea` partirdecesmotspre´xeetsuxe. Exercice 5.3sruocraPcrare´ihequhi Soit le tableau d’entiersTab={0, 2, 3, 4, 6, 7, 9, 10, 12, 13, 14, 16, 20} et la fonctionremplirTableauArbrevue en cours (annexe C). Dessinerlarbrebinaireproduitparlappel`aremplirTableauArbre(Tab).
Exercice 5.4Parcours en profondeur Utiliser un parcours en profondeur pour ecrire les fonctions : 1. Ecrireune fonction qui compte le nombre de feuilles dans un arbre binaire. 2. Ecrireune fonction qui calcule la hauteur d’un arbre binaire. 3. Ecrireune fonction qui retourne le minimum des valeurs contenues dans un arbre binaire.
Exercice 5.5galit´enance,´eAppraet
1.Ecrireunefonctionquitestesiun´el´ementappartient`aunarbrebinaire. 2.Ecrireunefonctionquitestele´galit´ededeuxarbresbinaires. 3. Ecrire une fonction qui teste si un arbrebinaire est un sous arbre d’un autre arbre binaire.
Exercice 5.6Arbre binaire complet On appellearbre binaire completun arbre binaire tel que chaque sommet interne a exactement 2 fils. 1. Donnerdes exemples d’arbres binaires complets. 2. Ecrireune fonction qui teste si un arbre binaire est complet.
2
Exercice 5.7Arbre binaire parfait On appellearbre binaire parfaitun arbre binaire complet dans lequel toutes lesfeuillessont`alameˆmehauteurdanslarbre. 1. Donnerdes exemples d’arbres binaires parfaits. 2. Ecrireune fonction qui teste si un arbre binaire est parfait.
Exercice 5.8Arbre binaire quasiparfait On appellearbre binaire quasiparfaittnemrepainaibrebunarleelneut´tvefria grignot´edune´tageenbas`adroite. 1. Donnerdes exemples d’arbres binaires quasiparfaits. 2. Ecrireune fonction qui teste si un arbre binaire est quasiparfait.
Exercice 5.9qite´mhtirasnoisesprexdontiuaalvEues Onsupposedonnerunarbrebinairerepr´esentantuneexpressionarithme´tique contenantdesentiersetdesope´rateursbinaires+et*. Si l’expression est bien form´ee(correcte)alorslarbrebinaireestcomplet.Chaquefeuilledecetarbre contientdoncunentieretchaquenoeudinterneunope´rateur(lundessymboles +ou*). On adopte comme convention que le symbole+e´doctsete1rap*par 2.
Ecrire une fonctionvaleurExpression( val A: arbreBinaire)uealuqve´i lavaleurdelexpressionrepre´sent´eeparunarbrebinairesilarbreestcomplet sinon renvoieNIL, en visitant une et une seule fois tous les noeuds de l’arbre (un seul parcours de l’arbre).
Proble`mer´ecurrent(notreldariane) Exercice 5.10Gestion d’une piste d’atterrissage des avions
Un avion est un enregistrement contenant : lindicatif(6caracte`res) ladestination(30caract`eres) lautonomier´esiduelledecarburantcompt´eeenheuresdevol(entier) deuxbool´eensindiquantsilyaunpiratea`bordetsilyalefeu. 1.D´enirlesstructuresdedonn´eesn´ecessaires. 2. Ecrirela fonctionerit´Priolpemp`altnoedoecs.eitslieegtasiquain 3.Envisagerlecasdesuppressiondune´le´mentquelconquedelalelorsque lepirateamissamenacedede´tournement`aex´ecution. Quelles sont les notions que vous venez de voir qui peuvent permettre d’amorcer le fil d’ariane?
3
Annexe AType abstraitarbreBinaire
arbreBinaire= curseur; sommet= curseur;
Crat´eoin fonction creerArbreBinaire(val Racine:objet):sommet; esc`Ac fonction getValeur(val S:sommet):objet; fonction filsGauche(val S:sommet):sommet; fonction filsDroit(val S:sommet):sommet; fonction pere(val S:sommet):sommet; Modification fonction setValeur(ref S:sommet, val x:objet):vide; fonction ajouterFilsGauche(ref S:sommet, val x:objet):vide; fonction ajouterFilsDroit(ref S:sommet, x:objet):vide; fonction supprimerFilsGauche(ref S:sommet):vide; fonction supprimerFilsDroit(ref S:sommet):vide; fonction detruireSommet(ref S:sommet):vide;
Annexe BIraitabsttypenoudatitmenepm´larbreBinaire
cellule=structure info:objet; gauche: sommet; droit: sommet; pere: sommet; finstructure sommet=^cellule;
4
Annexe CiberrianudnbranrustioctonCeluantabrduartie`ap
fonction remplirTableauArbre(ref T:tableau[1..N] d’entier): arbreBinaire d’entier; var A:arbreBinaire d’entier; var F: file de sommet; var s:sommet; var i:entier; debut creerFile(F); A= creerArbreBinaire(T[1]); enfiler(F, A); tmp= 2; tantque 2*tmp1 <= N faire pour i= tmp a 2*tmp1 par pas de 2 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 pour i=tmp a N1 par pas de 2 faire s= getValeur(F); defiler(F); ajouterFilsGauche(s, T[i]); ajouterFilsDroit(s, T[i+1]); finpour; si N mod 2 == 0 alors ajouterFilsGauche(getValeur(F), T[N]) finsi detruireFile(F); retourner(A); fin
5
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.