DEV 3.2

Arbres

À savoir Les arbres comme structures concrètes de données

Ce que en informatique on nomme arbre est une évolution directe du concept de liste chaînée. Il suffit pour cela de permettre à chaque maillon de contenir plusieurs références à d'autres maillons. On interdit cependant les références circulaires pour en simplifier le parcours.

À savoir Le vocabulaire des arbres

Un maillon est nommé nœud dans cette nouvelle structure. L'élément qu'il contient est son étiquette.

Par analogie avec les arbres généalogiques, un nœud contenant une référence est appelé nœud parent et le nœud référencé est appelé nœud enfant. Par analogie avec les véritables arbres, le nœud de départ est nommé racine et les nœuds sans enfants sont nommés feuilles.

Les arbres homogènes contiennent des nœuds d'une seule classe. Les arbres hétérogènes permettent plusieurs classes de nœuds (en Java, par substitution).

Un arbre est binaire si aucun de ses nœuds ne peut avoir plus de deux enfants.

Répertoires. Écrivez une application qui prend sur la ligne de commande le nom d'un répertoire, puis construit un arbre homogène représentant ce répertoire et son contenu (fichiers, sous-répertoires et leur contenu, etc...) en stockant le nom de chaque élément. L'application devra ensuite afficher l'arbre obtenu en s'inspirant de la commande tree (en plus simple).
```
bob@box:~$ java Repertoires toto
toto
  sous1
    fichier1
    fichier2
  sous2
    fichier3
  fichier4
```
Le constructeur et la méthode d'affichage devront être récursifs. L'exploration de l'arborescence des répertoires est possible grâce à la méthode listFiles de la classe File.
Préfixe. Reprenez le premier exercice du sujet sur les piles, et remplacez l'affichage du résultat par un affichage de l'expression en notation polonaise (non inversée).
```
bob@box:~$ java Prefixe 8 6 1 2 + 9 + + / 5 x 7 -
= - x / 8 + 6 + + 1 2 9 5 7
```
Remarque Pour cela vous devez transformer l'expression arithmétique en un arbre de syntaxe abstraite, hétérogène et binaire. On employera la même pile que dans l'exercice d'origine pour y parvenir, mais on y stockera des nœuds plutôt que des entiers.
Infixe. Reprenez l'exercice précédent, en affichant le résultat en notation classique (avec un maximum de parenthèses pour ne pas avoir à se soucier des priorités).
```
bob@box:~$ java Infixe 8 6 1 2 + 9 + + / 5 x 7 -
= (((8/(6+((1+2)+9)))x5)-7)
```
Variables. Reprenez l'exercice précédent, en permettant l'utilisation de variables (une lettre majuscule) dans les expressions.
```
bob@box:~$ java Variables U 6 1 2 + V + + / V x 7 -
= (((U/(6+((1+2)+V)))xV)-7)
```
Remarque On ne stocke généralement pas le nom des variables dans l'arbre mais seulement un numéro d'identification. C'est la table des symboles qui donne son numéro à chaque variable. Quelle est la structure de donnée la plus adaptée pour cette table ?

Ajoutez ensuite une deuxième phase où on demande à l'utilisateur la valeur de chaque variable, puis on évalue l'expression.
```
bob@box:~$ java Variables U 6 1 2 + V + + / V x 7 -
= (((U/(6+((1+2)+V)))xV)-7)
U ? 29
V ? 5
= 3
```

Développement 3.2

Arbres