TD10 Corrige [PDF]

Zitiervorschau

É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

0

12

2

24 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. 7 3

13

1

5

0

24

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. 7 3 1 0

24 5

2

2

17

30

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. 7 2 1

24 5

17

30

0

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 val 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 val 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 val 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); } }

6