Arbres binaires

1. 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.
2. Modifier la fonction main du fichier tp07.c pour qu'elle crée l'arbre suivant, en utilisant la fonction create_node :
   
   
   

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

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

1. 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.
   
   
   
   
   
2. 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() {
   
     node *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.
3. La fonction void write_tree_aux(node *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.
4. 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.

Ajouter à tree.h et à tree.c, le prototype et la définition pour la fonction node *scan_tree(void) qui construit un arbre binaire à partir d'entiers lus au clavier. La fonction renvoie un pointeur sur la racine de l'arbre construit. 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) :

• alea1.txt
• alea2.txt
• alea3.txt
• alea4.txt
• complet.txt

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

Ajouter à tree.h et à tree.c, les prototypes et les définitions des fonctions suivantes :

1. int sum(node *t) qui renvoie la somme de tous les éléments de l'arbre t ;
2. int height(node *t) qui renvoie la hauteur de l'arbre t ;
3. int sum_depth(node *t) qui renvoie la somme de la profondeur de tous les noeuds de l'arbre t où on se rappelle que la profondeur d'un noeud est la distance entre la racine et le noeud.

On considère un arbre binaire de hauteur inférieure à une certaine constante MAX_HEIGHT. On souhaite avoir une fonction void display_paths(node *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_aux(node *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 de la fonction void display_paths(node *t). La fonction annexe, void display_paths_aux(node *t, int buffer[], int index) sera placé dans tree.c uniquement.