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
.
![[*]](froidevaux_fig_19.jpg)
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 :
compter (val A : arbreBinaire): entier qui compte le
nombre de feuilles dans A.
hauteur (val A : arbreBinaire): entier qui calcule la hauteur de A.
valeur_minimum(val A : arbreBinaire): entier qui retourne le minimum des valeurs contenues dans A.
Exercice 4.4 Appartenance,égalité
Exercice 4.5 Arbre binaire complet
On appelle arbre binaire complet un arbre binaire tel
que chaque sommet possède 0 ou 2 fils.
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.
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.
arbreBinaire_quasi_parfait(val A:arbreBinaire ): booleen;