:: Enseignements :: ESIPE :: E3INFO :: 2013-2014 :: Algorithmique ::

Arbres binaires

Le but de ce TP est de manipuler les arbres binaires. On implémente des parcours en profondeur et des fonctions récursives de base sur des arbres binaires. On implémente également des fonctions pour visualiser les arbres en utilisant l'outil dot.

Exercice 1 - Compilation séparée

Les définitions de type suivantes permettent de représenter un arbre binaire d'entiers :

Créer un fichier arbre.h et mettre les définitions de type dans le fichier.
Ajouter à arbre.h le prototype d'une fonction Noeud *allouerNoeud(int elt). Créer un fichier arbre.c et y ajouter la définition de la fonction.
Créer un fichier tp08.c avec une fonction main qui utilise la fonction allouerNoeud pour créer l'arbre suivant :
Créer un makefile qui compile, si besoin, les deux fichiers arbre.c et tp08.c.

Exercice 2 - Parcours et construction

Ajouter à arbre.h et à arbre.c, les prototypes et les définitions pour les fonctions suivantes vues en td :

void afficherPrefixe(Arbre arb) qui affiche les valeurs des noeuds de l'arbre arb en ordre préfixe ;
void afficherInfixe(Arbre arb) qui affiche les valeurs des noeuds de l'arbre arb en ordre infixe ;
void afficherPostfixe(Arbre arb) qui affiche les valeurs des noeuds de l'arbre arb en ordre postfixe ;
int construireArbre(Arbre *arb) qui construit un arbre binaire à partir d'entiers lus au clavier. La fonction renvoie 1 en cas de réussite et 0 sinon. Pour tester votre fonction, vous pouvez utiliser les arbres suivants :

L'exemple du td : 3 5 12 0 0 1 4 0 0 0 2 0 7 0 0

D'autres exemples (télécharger les fichiers, puis copier-coller dans le terminal) :

Exercice 3 - Mesures

Ajouter à arbre.h et à arbre.c, les prototypes et les définitions pour les fonctions suivantes vues en td :

int hauteur(Arbre arb) qui renvoie la hauteur de l'arbre arb ;
int nombreNoeuds(Arbre arb) qui renvoie le nombre de noeuds de l'arbre arb ;
int nombreNoeudsInternes(Arbre arb) qui renvoie le nombre de noeuds internes de l'arbre arb ;
int nombreFeuilles(Arbre arb) qui renvoie le nombre de feuilles de l'arbre arb ;
int nombreDeuxFils(Arbre arb) qui renvoie le nombre de noeuds de l'arbre arb possédant exactement 2 fils.

Exercice 4 - Nettoyage

Ajouter à arbre.h le prototype d'une fonction récursive void libererArbre(Arbre arb) qui libère toute mémoire associée à l'arbre arb.

Exercice 5 - Visualisation

Copier le code suivant dans un fichier arbre.dot.
```
digraph arbre {
  node [shape=record,height=.1]
  edge [tailclip=false, arrowtail=dot, dir=both];

  n0 [label="<gauche> | <valeur> 5 | <droit>"];
  n0:gauche:c -> n1:valeur;
  n1 [label="<gauche> | <valeur> 7 | <droit>"];
  n0:droit:c -> n2:valeur;
  n2 [label="<gauche> | <valeur> 3 | <droit>"];
  n2:droit:c -> n3:valeur;
  n3 [label="<gauche> | <valeur> 1 | <droit>"];

}
```
Dans l'exemple, les noms n0, ..., n3 sont des noms qui désignent les quatre noeuds de l'arbre. Sur la ligne 5, le noeud qui contient l'entier 5 est déclaré. Puis, sur la ligne 6, on déclare que ce noeud a un fils gauche, le noeud n1: on relie n0:gauche:c avec n1:valeur. Cela dit au programme dot de dessiner une flèche du centre de la partie gauche du noeud n0 vers la partie valeur du noeud n1.

Vous trouverez la documentation du langage DOT sur le lien suivant :
- La documentation du langage DOT.
Taper dans un terminal dot -Tps2 arbre.dot > arbre.ps pour construire le graphique et gv arbre.ps pour le visualiser.
Écrire une fonction void ecrireDebut() qui affiche les trois premières lignes et une fonction void ecrireFin() qui affiche la dernière ligne de l'exemple dans un terminal.
À partir de l'exemple, écrire une fonction void ecrireArbre(Arbre arb) qui prend en argument un arbre quelconque et qui génère le code pour le visualiser avec le programme dot. Pour l'exemple ci-desus, la fonction génèrera les lignes 5 à 11. Donc, si arb contient l'arbre de la figure, on génère le code de l'exemple en lançant les trois fonctions comme suit :
```
ecrireDebut();
ecrireArbre(arb);
ecrireFin();
```
Pour donner un nom unique à chaque noeud, vous pouvez donner les noms en utilisant les adresses mémoire des noeuds. Par exemple, pour un Noeud *tmp, vous pouvez utiliser printf("n%p", tmp) pour afficher son nom.
Changer les trois fonctions précédentes pour qu'elles écrivent le code DOT sur un fichier. Réécrire les trois fonctions en leur donnant les prototypes FILE *ecrireDebut(char *nom), void ecrireFin(FILE *f) et void ecrireArbre(FILE *f, Arbre arb) La fonction ecrireDebut ouvrira un fichier avec le nom nom pour écriture et y écrit les trois premières lignes. La fonction ecrireArbre écrit le code pour la visualisation de l'arbre arb sur le fichier *f. La fonction ecrireFin fermera le fichier après avoir écrit la dernière ligne.

Exemple d'utilisation :
```
FILE *f;
f = ecrireDebut("arbre.dot");
ecrireArbre(f, arb);
ecrireFin(f);
```

Exercice 6 - Chemins de la racine aux feuilles

On considère un arbre binaire de hauteur inférieure à une certaine constante HAUT_MAX. On souhaite avoir une fonction void afficherChemins(Arbre arb) qui permet l'affichage de tous les chemins menant de la racine aux feuilles dans l'ordre d'un parcours en profondeur préfixe. Ainsi, pour l'arbre ci-dessous:
la fonction doit afficher
```
7 2 9 1
7 2 9 5
7 2 3
7 4 6 3
7 4 6 1
```
On utilisera une fonction auxiliaire void afficherCheminsAux(Arbre arb, int tampon[], int indice) où tampon est un tableau de taille HAUT_MAX déclaré dans la fonction afficherChemins et indice indique la première case vide libre de tampon.
Ajouter à arbre.h et à arbre.c, le prototype et la définition pour la fonction void afficherChemins(Arbre arb). La fonction annexe, void afficherCheminsAux(Arbre arb, int tampon[], int indice) sera placé dans arbre.c uniquement.