École préparatoire aux sciences et techniques, Annaba
Année universitaire 2012/2013
Module : Informatique 2
Série de TD n˚10 : Arbres
Solution
Rappel sur les arbres
1. Donnez une structure de données qui permet de representer un arbre binaire (cette
structure sera utilisé dans les exercices qui suivent).
struct noeud {
int val;
noeud * g;
noeud * d;
};
2. Dans un arbre, comment appelle-t-on le noeud qui n’a pas d’ascendant (parent) ?
La racine
3. Dans un arbre, comment appelle-t-on les noeuds qui n’ont pas de descendants (fils) ?
Les feuilles
4. Comment indiquer qu’un arbre est vide ?
racine = NULL; //Affecter NULL à sa racine
5. Quels sont les trois types de parcours d’un arbre ?
infixe, postfixe et préfixe
6. Quel type de parcours fournit les valeurs d’un ABR en ordre croissant ?
Le parcours infixe
1
Exercice 1
1. Donnez l’arbre binaire de recherche obtenu en inserant successivement les valeurs
suivantes : 7, 13, 3, 12, 5, 1, 24, 0, 2, 17, 30
7
3 13
1 5 12 24
0 2 17 30
2. Donnez le parcours infixe de cet arbre.
0 1 2 3 5 7 12 13 17 24 30
3. Donnez le parcours préfixe de cet arbre.
7 3 1 0 2 5 13 12 24 17 30
4. Donnez le parcours postfixe de cet arbre.
0 2 1 5 3 12 17 30 24 13 7
5. Supprimez le noeud 12 de cet arbre.
Le noeud 12 est une feuille, donc il suffit de l’enlever.
3 13
1 5 24
0 2 17 30
6. Supprimez le noeud 13 de cet arbre.
Le noeud 13 possède un seul fils, donc il suffit de le remplacer
par son fils.
3 24
1 5 17 30
0 2
2
7. Supprimez le noeud 3 de cet arbre.
Le noeud 3 possède deux fils, donc il faut le remplacer avec
son prédécesseur direct (le noeud le plus à droite de son
fils gauche). Ensuite supprimer son prédécesseur direct
en utilisant l’une des deux suppressions.
2 24
1 5 17 30
Exercice 2
1. Écrire une fonction inserer qui permet d’inserer une valeur dans un ABR.
void inserer(noeud * & racine, int x) {
if (racine==NULL) {
racine = new noeud;
racine->val = x;
racine->g = NULL;
racine->d = NULL;
} else if (x>racine->val)
inserer(racine->d,x);
else
inserer(racine->g,x);
}
2. Écrire une fonction infixe qui parcours et affiche les valeurs d’un ABR dans un
ordre infixe.
void infixe(noeud * racine) {
if (racine!=NULL) {
infixe(racine->g);
cout << racine->val << "\t";
infixe(racine->d);
}
}
3. Écrire une fonction prefixe qui parcours et affiche les valeurs d’un ABR dans un
ordre préfixe.
void prefixe(noeud * racine) {
if (racine!=NULL) {
3
cout << racine->val << "\t";
prefixe(racine->g);
prefixe(racine->d);
}
}
4. Écrire une fonction postfixe qui parcours et affiche les valeurs d’un ABR dans un
ordre postfixe.
void postfixe(noeud * racine) {
if (racine!=NULL) {
postfixe(racine->g);
postfixe(racine->d);
cout << racine->val << "\t";
}
}
5. Écrire une fonction existe qui teste si une valeur donnée existe dans un ABR. La
fonction retourne true si la valeur existe et false sinon.
bool existe(noeud * racine, int x) {
if (racine==NULL)
return false;
else if (x==racine->val)
return true;
else if (x>racine->val)
return existe(racine->d,x);
else
return existe(racine->g,x);
}
6. Écrire une fonction taille qui calcule le nombre de noeuds d’un ABR.
int taille(noeud * racine) {
if (racine==NULL)
return 0;
else
return 1 + taille(racine->g) + taille(racine->d);
}
7. Écrire une fonction hauteur qui calcule la hauteur d’un ABR (la hauteur d’un ABR
est le nombre de noeuds entre la feuille la plus eloignée et la racine).
int hauteur(noeud * racine) {
if (racine==NULL)
return 0;
else
4
return 1 + max(hauteur(racine->g),hauteur(racine->d));
}
8. Écrire une fonction nombreFeuilles qui retourne le nombre de feuilles d’un ABR.
int nombreFeuilles(noeud * racine) {
if (racine==NULL)
return 0;
else if (racine->g==NULL && racine->d==NULL)
return 1;
else
return nombreFeuilles(racine->g) + nombreFeuilles(racine->d);
}
9. Écrire une fonction max qui retourne la plus grande valeur d’un ABR (supposez que
l’ABR n’est pas vide).
int max(noeud * racine) {
while (racine->d!=NULL)
racine = racine->d;
return racine->val;
}
10. Écrire une fonction supprimer qui supprime un élément d’un ABR.
void supprimer(noeud * & racine, int x) {
if (racine!=NULL) {
if (racine->val==x)
if (racine->g==NULL && racine->d==NULL) {
delete racine;
racine = NULL;
} else if (racine->g==NULL) {
noeud * p = racine;
racine = racine->d;
delete p;
} else if (racine->d==NULL) {
noeud * p = racine;
racine = racine->g;
delete p;
} else {
noeud * p = racine->g;
while (p->d!=NULL)
p = p->d;
racine->val = p->val;
supprimer(racine->g,p->val);
} else if (x>racine->val)
supprimer(racine->d,x);
5
else
supprimer(racine->g,x);
}
}
