TD No 4
from http://vernier.frederic.free.fr/Teaching/PimpA

Traversés et calculs dans des arbres.

Questions sans code à écrire

1. Un élément clé dans la définition d'un arbre, c'est la relation entre le noeud "père" et (la liste) de ses noeuds "fils". Nommez au moins 3 differentes manières de representer cette relation !
2. Un arbre n-aire, c'est quoi ?
3. Construisez un arbre de degrée 3 et discutez l'ordre des visites pour les stratégies suivantes:
   • Parcours en profondeur via préfixe.
   • Parcours en profondeur via infixe.
   • Parcours en profondeur via postfixe.
   • Parcours en largeur ("breadth-first" de gauche à droite).
4. Discutez le code incomplet pour EXO 4.1, EXO 4.2, EXO 4.3 ! Comment est-ce qu'on peut programmer des noeuds de "genres" différents comme "Value" et "Operation"?

Implémentations

5. EXO 4.1 Arbre sans références (postfix-representation dans un tableaux). Implantez les parties qui manquent (TODO dans le code).
   • Implantez les fonctions selectors get_left(int x) et get_right(int x). Indication: Il peut-etre utile d'implanter une fonction qui calcule la taille d'une expression dans "expr" d'abord.
   • Implantez print_infix_expr(int n), une fonction qui répresente l'arbre syntaxique comme string en infix-notation. Indication: Utilisez une variante de l'algorithme de traversée en infixe. (correct avec des paranthèses, mais pas nécessairement avec un nombre de paranthèses minimal).
   • Implantez calc_val_expr, qui fait l'évaluation d'une expression.
   • Construisez l'arbre syntaxique pour "(((2 * 3) + 4) * ((2 + 3) * 2))" et evaluez cette expression via calc_val_expr.
6. EXO 4.2 Arbre avec references (representation via "pointer" dans un tableaux). Implantez les bouts qui manquent.
   • Implantez la "structure de donnée" Arbre: les constructeurs mkValueNode et le mkOperatorNode et les selectors get_left et get_right.
   • Implantez print_infix_expr, une fonction qui répresente l'arbre syntaxique comme string en infix-notation (comme en 4.1).
   • Implantez calc_val_expr, qui fait une évaluation d'une expression.
   • Construisez l'arbre syntaxique pour "(((2 * 3) + 4) * ((2 + 3) * 2))" et evaluez cette expression via calc_val_expr.
7. EXO 4.3 [Optionel, MARCHE QUE SOUS LINUX! ] Arbre polyandique sans références (Une traversée du système de fichiers). Trouvez le "fichier régulier" de taille maximale, dans le répertoire ou ses sous-répertoires. Implantez les bouts qui manquent, cela veut dire la fonction int find_largest_file(string dir, string &name) .
   • Développez un schéma de récursion au delà des arbres binaires.
   • Re-utilisez les fonctions getLength et getdir.
   • Indication: la fonction getdir rend aussi les répertoires "." et "..". Prenez ces cas en compte pour éviter les cycles.