TP #3 : Arbres binaires

Objectifs

  • Savoir créer et utiliser une bibliothèque d’arbres d’entiers
  • Savoir coder quelques algorithmes de base sur les arbres

Contexte et préparation

Vous trouverez plusieurs fichiers pour vous aider à démarrer le TP:

  • https://www.dequidt.me/uploads/se/trees.c et https://www.dequidt.me/uploads/se/trees.h contenant des fonctions de base de traitement des arbres
  • https://www.dequidt.me/uploads/se/main.c un fichier qui permet d’utiliser ses fonctions
  • https://www.dequidt.me/uploads/se/tree2pdf.c un deuxième fichier qui permet de transformer un arbre en PDF
  • https://www.dequidt.me/uploads/se/samples/ un repertoire qui contient des fichiers de données à savoir balanced.dot balanced.pdf balanced.txt degenerated.dot degenerated.pdf degenerated.txt empty.dot empty.pdf empty.txt leaf.dot leaf.pdf leaf.txt unspecified.dot unspecified.pdf unspecified.txt

Questions du TP

  • Écrire la fonction cons_tree(...) qui construit un ABR (fait en cours).
  • Écrire la fonction mk_empty_tree(...)
  • Écrire la fonction is_empty(...)
  • Écrire la fonction is_leaf(...) tous des fonctions auxiliaires. (Fait en cours)
  • Écrire la fonction add(...) qui ajout un élément dans un ABR (arbre binaire de recherche, donc ordonné !). (Fait en cours)
  • Écrire la fonction print_tree(...) qui imprime un ABR par parcours récursif, en ordre ascendant (infixe).
  • Vérifier que la fonction de parcours précédente donne la même suite de valeurs pour les trois fichiers unspecified.txt, balanced.txt , degenerated.txt alors que ce sont des arbres différents (voir les dessins dans le répertoire samples/)
  • Écrire une fonction load_tree(...) qui construit un arbre d’entiers à partir d’un fichier.
  • Écrire une fonction free_tree(...) qui libère la mémoire utilisé par un arbre binaire.
  • Écrire une fonction d’impression print_rec_edges(…) qui imprime les couples (père =L=> fils) pour les fils gauches, et (père =R=> fils) pour les fils droits, d’un arbre donné. Ne pas imprimer les sous-arbres vides. À part la flèche =L/R=>, l’impression donne des arbres correspondant aux fichiers .dot fournis dans le répertoire samples/
  • Les fichiers .pdf ont été générés à partir des fichiers .dot (fournis dans samples/). Le format .dot est un format de représentation textuelle simple d’arbres [^1]. Visualisez le format de ces fichiers dans votre éditeur de texte préféré ou par la commande less. À partir de ce format .dot, la commande dot permet de générer une version visualisable (.pdf, .png,…) comme suit (en pdf par exemple) :
dot -Tpdf samples/balanced.dot -o samples/balanced.pdf

L’objectif est alors de générer de tels fichiers pour des arbres construits à partir de fichiers de données (tels que ceux fournis dans samples/*.txt).

Préparation : Un fichier tree2pdf.c plus conséquent est fourni qui : Génère, par appel à la fonction generate_dot, les fichiers .dot correspondants aux fichiers de données dont les noms ont été passés en paramètre (e.g. à partir de samples/balanced.txt on génère samples/balanced.dot). Transforme ces fichiers .dot en .pdf par appel système à la commande dot.

  • Programmer la fonction recursive_dot qui traite le cas général
  • Tester ensuite par la commande : ./tree2pdf samples/*.txt Vous devez retrouver les fichiers .dot et .pdf.