Ecole Supérieure d’Informatique Sba le
Sidi Bel Abbés
FICHE TD 8: les structures d'arbres
Exercice 1:
1 Écrire une fonction cree_arbre () qui prend en argument une valeur entière ainsi que deux
arbres et renvoie un arbre dont la racine contient cette valeur et les deux sous-arbres sont
ceux donnés en paramètre.
2 Écrire une fonction (récursive) detruit_arbre () qui libère la mémoire occupée par tous les
nœuds d'un arbre binaire.
3 Écrire une fonction (récursive) nombre_de_noeuds () qui calcule le nombre de nœuds d'un
arbre binaire.
Exercice 2: Arbres m-aire.
1- Ecrire un module qui permet de réaliser une recherche dans un fichier organisé sous forme
d'un arbre de recherche m-aire.
2- Soit Ins( e:Tenreg; nomf:chaine ) le module qui permet d'insérer une nouvelle valeur
(enregistrement ou clé/adr) dans le fichier. Pour le réaliser, utiliser le module recherche
Correcion Exercice 1 :
Revision
1
Correcion Exercice 2 :
Chaque nœud de l'arbre est représenté par un bloc d'E/S.
La structure générale d'un bloc est alors comme suit :
Type Tbloc = structure
Val : tableau[N-1] de typeqlq;
Fils : tableau[N] d'entier;
degré : entier;
Fin;
// enregistrements ou (clés-adr)
// numéros de blocs
// nb d'elt dans le tableau Fils
Parmi les caractéristiques d'un fichier vu comme arbre, il y a la racine. C'est le numéro du bloc
contenant la racine de l'arbre.
Par exemple, si l'arbre de la figure précédente était un fichier, le contenu du bloc d serait comme
suit:
Val 42 50 55 60
Fils -1 h -1 -1 i degré 5
1 2 3 4 5
alors que le contenu du bloc g serait :
Val 10
Fils -1 -1 degré 2
1 2 3 4 5
Question 1 : Le module suivant permet de réaliser une recherche dans un fichier organisé
sous forme d'un arbre de recherche m-aire :
Rech( c:Typeqlq; nomf:chaine; var trouv:booleen; var i,j,prec:entier)
/*
* recherche c et retourne en plus du booléen trouv, le num de bloc (i) qui contient c ainsi que sa
* position (j) dans Val et le num (prec) du bloc qui précède i.
* Si c n'existe pas, alors i sera positionnée à -1 et prec indique le num du dernier bloc visité.
* la position ou devrait se trouver c dans le bloc prec est indiquée par j.
*/
Debut
Si ( nomf <> '' ) Ouvrir( F, nomf, 'A') Fsi;
i ← Entete(F,1);
// le num du bloc racine
prec ← -1;
j ← 1;
trouv ← FAUX;
TQ ( Non trouv et i <> -1 )
LireDir( F, i, buf );
// recherche interne dans le bloc ...
j ← 1; stop ← FAUX ;
TQ ( Non trouv et j < buf.degre et Non stop )
Si ( c = buf.Val[j].cle ) trouv ← VRAI
Sinon Si ( c > buf.Val[j].cle ) stop ← VRAI Sinon j ← j+1 Fsi
Fsi
FTQ;
// fin de la recherche interne.
Si ( Non trouv )
prec ← i; i ← buf.Fils[j]
Fsi
FTQ;
Si ( nomf <> '' ) Fermer(F) Fsi;
Fin
Question 2 : L'insertion d'une nouvelle valeur (enregistrement ou clé/adr) dans le fichier
utilise la recherche:
Ins( e:Tenreg; nomf:chaine )
Debut
Ouvrir( F, nomf, 'A' );
Si ( Entete(F,1) = -1 ) // Si le fichier est vide
i ← AllocBloc( F );
Aff_entete( F, 1, i );
// la nouvelle racine
buf.degre ← 1;
buf.Val[1] ← e;
buf.Fils[1] ← -1;
buf.Fils[2] ← -1;
EcrireDir( F, i, buf );
Sinon
Rech( e.cle, '', trouv, i, j, prec );
Si ( Non trouv )
// si le dernier bloc visité n'est pas plein, on y insère l'enreg e ...
Si ( buf.degre < N )
// décalages interne à partir de j ...
Pour k ← buf.degre, j+1, -1 // boucle arrière avec pas = -1
buf.Val[k] ← buf.Val[k-1];
buf.Fils[k+1] ← buf.Fils[k];
FinPour
buf.Val[j] ← e;
// insérer e à la pos j
buf.Fils[j+1] ← -1;
// et son « fils droit » à nil
buf.degre ← buf.degre + 1; // incrémenter le degré
EcrireDir( F, prec, buf );
Sinon // si le bloc est plein, il faut allouer un nouveau ...
i ← AllocBloc( F );
// et le chaîner avec le précédent
buf.Fils[j] ← i
EcrireDir( F, prec, buf );
// insérer e à la pos 1 du nouveau bloc ...
buf.degre ← 1;
buf.Val[1] ← e;
buf.Fils[1] ← -1;
buf.Fils[2] ← -1;
EcrireDir( F, i, buf )
Fsi
Fsi // Non trouv
Fsi // Entete(F,1) = -1
Fermer(F)
Fin
// entete(F,2) : désigne le dernier bloc en zone de débordement (initalement N+1)
