On considère le type abstrait
arbreBinaire de type_predefini avec les
primitives suivantes:
fonction valeurSommet(val A: arbreBinaire de type_predefini,
val S: sommet): type_predefini;
fonction racine(val A: arbreBinaire de type_predefini): sommet;
fonction filsGauche(val A: arbreBinaire de type_predefini, val S: sommet): sommet;
fonction filsDroit(val A: arbreBinaire de type_predefini, val S: sommet): sommet;
fonction pere(val A: arbreBinaire de type_predefini, val S: sommet): sommet;
fonction CreerArbreBinaire(ref A: arbreBinaire de type_predefini,
val racine: type_predefini): vide;
fonction ajouterFilsGauche(val x: type_predefini,
ref A: arbreBinaire de type_predefini,val S: sommet): vide;
fonction ajouterFilsDroit(val x: type_predefini,
ref A: arbreBinaire de type_predefini, val S: sommet): vide;
fonction supprimerFilsGauche(ref A: arbreBinaire de type_predefini, val S: sommet): vide;
fonction supprimerFilsDroit(ref A: arbreBinaire de type_predefini, val S: sommet): vide;
Exercice 4.1 Parcours
Soit l'arbre binaire dont les feuilles sont étiquetées
avec les nombres naturels illustré avec les nombres naturels illustré ci-dessous.

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).
fonction remplirTableauArbre(
val T: tableau[1..N] d'entiers): arbreBinaire d'entiers;
var A: arbreBinaire d'entiers;
var F: file de sommets;
var S: sommet;
var i, tmp, s: entier;
debut
creerFile(F);
creerArbreBinaire(A, T[1]);
enfiler(F, racine(A));
tmp= 2;
tantque 2*tmp-1 <= N faire
pour i allant de tmp a 2*tmp - 1 par pas de 2 faire
S= valeur(F);
defiler(F);
ajouterFilsGauche(T[i], A, S);
enfiler(filsGauche(A, S));
ajouterFilsDroit(T[i+1], A, S);
enfiler(filsDroit(A, S));
finpour
tmp= tmp * 2;
fintantque
pour i allant de tmp a N par pas de 2 faire
S= valeur(F);
defiler(F);
ajouterFilsGauche(T[i], A, S);
ajouterFilsDroit(T[i+1], A, S);
finpour
retourner(A);
fin
finfonction
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;