next up previous
suivant: À propos de ce

Soit le type abstrait arbreBinaire de type_predefini représenté comme il suit:

type arbreBinaire= structure
                     tailleStock: entier
                     arbre: tableau[1..tailleStock] d'elements de ^type_predefini
                   finstructure
type sommet= entier
type type_predefini= entier

On souhaite implémenter le type abstrait arbreBinaire de type_predefini en utilisant le parcours hiérarchique (voir la fonction remplirTableauArbre vue en cours). L'idée de base est de stocker la racine de l'arbre A dans le premier élément du tableau A.arbre[1] et ensuite, pour chaque élément A.arbre[i], stocker les fils gauche et droit resp. dans A.arbre[2i] et A.arbre[2i+1].

arbreBinaire= structure
                 tailleStock: entier
                 arbre: tableau[1..tailleStock] d'elements de ^type_predefini
              finstructure
type sommet= entier
type type_predefini= entier

On dispose des primitives suivantes:

fonction valeurSommet(val arbreBinaire A, val sommet s): type_predefini;
fonction valeur(val A: arbreBinaire, val s: sommet): ^type_predefini;
fonction sommet racine(val A: arbreBinaire) : sommet;
fonction filsGauche(val A: arbreBinaire, val s: sommet) : sommet;
fonction filsDroit(val A: arbreBinaire, val s: sommet) : sommet;
fonction pere(val A: arbreBinaire, val s: sommet) : sommet;
fonction CreerArbreBinaire(ref A: arbreBinaire, val racine: type_predefini) : vide;
fonction ajouterFilsGauche(val x: type_predefini, ref A: arbreBinaire,
                                                  ref s: sommet) : vide;
fonction ajouterFilsDroit(val x: type_predefini, ref A: arbreBinaire,
                                                 ref s: sommet) : vide;
fonction  supprimerFilsGauche(ref A: arbreBinaire, ref s: sommet) : vide;
fonction supprimerFilsDroit(ref A: arbreBinaire, ref s: sommet) : vide;

Exercice 5.1 Structures de données
L'implémentation d'un arbre est illustré ci-dessous. On ajoute une feuille au dernier niveau. Dessiner la nouvelle structure.

Exercice 5.2 Construction
Dessiner l'arbre binaire construit par la fonction suivante:

fonction creer_arbre_fig_1(ref a: arbreBinaire): vide
  var s, s2, s3, s4, s5, s7: sommet;
  debut 
    CreerArbreBinaire(a, 1);
    sommet s= racine(a);
    ajouterFilsGauche(2, a, s);
    sommet s2= filsGauche(a, s);
    ajouterFilsGauche(4, a, s2);
    sommet s4= filsGauche(a, s2);
    ajouterFilsDroit(6, a, s4);
    ajouterFilsDroit(3, a, s);
    sommet s3= filsDroit(a, s);
    ajouterFilsDroit(5, a, s3);
    sommet s5= filsDroit(a, s3);
    ajouterFilsGauche(7, a, s5);
    sommet s7= filsGauche(a, s5);
    ajouterFilsDroit(9, a, s7);
    ajouterFilsDroit(8, a, s5);
  fin
finfonction
Quelle est la valeur minimale de tailleStock pour pouvoir contenir cet arbre?

Exercice 5.3 Primitives
Compléter l'implémentation vue en cours par les primitives:

valeur, filsDroit, pere, ajouterFilsDroit, supprimerFilsDroit

Exercice 5.4 Exemples
Écrire les fonctions:

fonction est_feuille(val A: arbreBinaire, val s: sommet): booleen;
fonction hauteur(val A: arbreBinaire): vide;
fonction afficher_arbre_parcours_prefixe(val A: arbreBinaire): vide;





Maylis Delest 2007-10-31