next up previous
suivant: Problème récurrent ( notre

On considère le type abstrait arbreBinaire d'objet avec les primitives suivantes:

arbreBinaire= sommet

fonction créerArbreBinaire(val Racine:objet):sommet;

fonction getValeur(val S:sommet):objet;
fonction filsGauche(val S:sommet):sommet;
fonction filsDroit(val S:sommet):sommet;
fonction pere(val S:sommet):sommet;

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;

Exercice 4.1 Parcours
Soit l'arbre binaire dont les feuilles sont étiquetées avec les nombres naturels illustré sur Figure
.

[*]
  1. Donner les mots correspondants resp. à son parcours préfixe, infixe et postfixe.
  2. Existe-t-il un arbre binaire à 8 sommets dont le mot préfixe est 12345678 et le mot suffixe est
    1. 53247681 ?
    2. 43527681 ?
  3. Donner le principe d'un algorithme pour reconstruire un arbre binaire à partir de ces mots préfixe et suffixe.


Exercice 4.2 Parcours hiérarchique
Soit le tableau d'entiers Tab={0, 2, 3, 4, 6, 7, 9, 10, 12, 13, 14, 16, 20}
et la fonction remplirTableauArbre vue en cours. Dessiner l'arbre binaire produit par l'appel à remplirTableauArbre(Tab).



Exercice 4.3 Parcours en profondeur
Utiliser un parcours en profondeur pour ecrire les fonctions :

  1. compter (val A : arbreBinaire): entier qui compte le nombre de feuilles dans A.
  2. hauteur (val A : arbreBinaire): entier qui calcule la hauteur de A.
  3. valeur_minimum(val A : arbreBinaire): entier qui retourne le minimum des valeurs contenues dans A.



Exercice 4.4 Appartenance,égalité

  1. Ecrire une fonction qui teste si un élément appartient à un arbre binaire.
  2. Ecrire une fonction qui teste l'égalité de deux arbres binaires.
  3. Ecrire une fonction qui teste si un arbre binaire est un sous arbre d'un autre arbre binaire.



Exercice 4.5 Arbre binaire complet
On appelle arbre binaire complet un arbre binaire tel que chaque sommet possède 0 ou 2 fils.

  1. Donner des exemples d'arbres binaires complets.
  2. Ecrire une fonction qui teste si un arbre binaire est complet
    arbreBinaire_complet(val A:arbreBinaire ): booleen;



Exercice 4.6 Arbre binaire parfait
On appelle arbre binaire parfait un arbre binaire (complet) tel que chaque sommet soit père de deux sous arbres de même hauteur.

  1. Donner des exemples d'arbres binaires parfaits.
  2. Ecrire une fonction qui teste si un arbre binaire est parfait.
    arbreBinaire_parfait(val A:arbreBinaire ): booleen;



Exercice 4.7 Arbre binaire quasi-parfait
On appelle arbre binaire quasi-parfait un arbre binaire parfait éventuellement grignoté d'un étage en bas à droite.

  1. Donner des exemples d'arbres binaires quasi-parfaits.
  2. Ecrire une fonction qui teste si un arbre binaire est quasi-parfait
    arbreBinaire_quasi_parfait(val A:arbreBinaire ): booleen;




next up previous
suivant: Problème récurrent ( notre
Maylis Delest 2008-10-03