:: Enseignements :: ESIPE :: E3INFO :: 2015-2016 :: 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 - Premier arbre

Récupérer l'archive Base.zip et extraire les fichiers dans votre répertoire de travail. Les fichiers tree.h et tree.c contiennet les définitions de type pour représenter un arbre binaire d'entiers ainsi qu'une fonction pour allouer un noeud. Makefile permet de générer un exécutable de nom ./tp07.
Modifier la fonction main du fichier tp07.c pour qu'elle crée l'arbre suivant, en utilisant la fonction allocate_node :

Exercice 2 - Parcours en profondeur

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

void display_prefix(tree t) qui affiche les valeurs des noeuds de l'arbre t en ordre préfixe ;
void display_infix(tree t) qui affiche les valeurs des noeuds de l'arbre t en ordre infixe ;
void display_suffix(tree t) qui affiche les valeurs des noeuds de l'arbre arb en ordre suffixe ;
Tester vos fonctions sur l'arbre créé dans l'exercice précédent.

Exercice 3 - 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="<left> | <value> 5 | <right>"];
  n0:left:c -> n1:value;
  n1 [label="<left> | <value> 7 | <right>"];
  n0:right:c -> n2:value;
  n2 [label="<left> | <value> 3 | <right>"];
  n2:right:c -> n3:value;
  n3 [label="<left> | <value> 1 | <right>"];

}
```
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:left:c avec n1:value. Cela dit au programme dot de dessiner une flèche du centre de la partie left du noeud n0 vers la partie value 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 -o arbre.ps | ps2pdf arbre.ps pour construire le graphique et evince arbre.pdf pour le visualiser.
Dans l'archive Base.zip se trouvent les fichiers visualtree.h et visualtree.c. Essayer la fonction main suivante, compiler et exécuter :
```
#include "tree.h"
#include "visualtree.h"
#include <stdlib.h>
#include <stdio.h>

int main() {

  tree t = NULL;
  write_tree(t);
  system("evince current-tree.pdf &");

  return 0;
}
```
La fonction write_tree dans visualtree.h génère le fichier current-tree.pdf et la fonction main ouvre ce fichier dans le visualiseur evince.
La fonction void write_tree_aux(tree t) ignore pour l'instant l'argument t. Elle construit simplement un arbre codé en dur, génère le code DOT correspondant dans le fichier current-tree.dot et convertit ce fichier en pdf. Modifier cette fonction dans le fichier visualtree.c pour qu'elle génère le code DOT qui correspond à l'arbre t donné en argument.
Dans la suite, vous pouvez utiliser la fonction write_tree pour vérifier que vos arbres sont bien construits. Noter que si vous laissez evince ouvert (lancé en arrière-plan avec evince current-tree.pdf &) alors le visualiseur affiche automatiquement les mises à jour du fichier current-tree.pdf. Donc, si votre programme fait plusieurs appels à la fonction write_tree, alors vous pouvez suivre les modifications de l'arbre dans le visualiseur.

Exercice 4 - Construction

Ajouter à tree.h et à tree.c, le prototype et la définition pour la fonction int scan_tree(tree *t) 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 5 - Nettoyage

Ajouter à tree.h le prototype d'une fonction récursive void free_tree(tree *t) qui libère toute mémoire associée à l'arbre *t.

Exercice 6 - Mesures

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

int height(tree t) qui renvoie la hauteur de l'arbre t ;
int count_nodes(tree t) qui renvoie le nombre de noeuds de l'arbre t ;
int count_internal_nodes(tree t) qui renvoie le nombre de noeuds internes de l'arbre t ;
int count_leaves(tree t) qui renvoie le nombre de feuilles de l'arbre t ;
int count_full_nodes(tree t) qui renvoie le nombre de noeuds de l'arbre t possédant exactement 2 fils.

Exercice 7 - Chemins de la racine aux feuilles

On considère un arbre binaire de hauteur inférieure à une certaine constante MAX_HEIGHT. On souhaite avoir une fonction void display_paths(tree t) 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 display_paths(tree t, int buffer[], int index) où buffer est un tableau de taille MAX_HEIGHT déclaré dans la fonction display_paths et index indique la première case vide libre de buffer.
Ajouter à tree.h et à tree.c, le prototype et la définition pour la fonction void display_paths(tree t). La fonction annexe, void display_paths_aux(tree t, int buffer[], int index) sera placé dans tree.c uniquement.