Arbres

1 - Arbres binaires étiquetés

Aujourd'hui nous allons manipuler des arbres. Les arbres sont des structures de données constituées de noeuds interconnectés. Il ont pour particularités :

de ne pas former de cycles, aucun noeud n'est relié à lui même par l'intermédiaire d'une chaîne de connexions à d'autres noeuds ;
d'être connexe, il existe une chaîne de connexions entre toute paire de noeuds (sinon c'est une forêt).

Nos arbres seront en outre :

enracinés, si l'arbre n'est pas vide, un noeud particulier est appelé racine, tous les autres noeuds auxquels il est connecté sont ses fils ;
binaires, tout noeud a, au plus, un père et deux fils ;
étiquetés, tout noeud est associé à une étiquette. Dans un premier temps, pour simplifier, nous prendrons un entier.

Concernant un noeud, nous dirons qu'il s'agit :

d'une feuille s'il n'a pas de fils ;
d'un noeud interne sinon.

En termes d'implémentation, nous définirons donc un arbre à l'aide d'une classe contenant un attribut racine qui pourra :

valoir null, si l'arbre est vide
être une référence à un triplet constitué :
- d'une référence à un noeud appelé fils gauche ou sous arbre gauche, pouvant être vide (null) ;
- d'une étiquette (un entier) ;
- d'une référence à un noeud appelé fils droit ou sous arbre droit, pouvant être vide (null).

Vous pouvez remarquer qu'un sous arbre est défini par un noeud, racine de ce sous arbre, est par tous les noeuds descendant de cette racine. Il n'y a pas vraiment de différence entre un arbre et un sous arbre si ce n'est l'objet de la classe Arbre qui va autour de l'arbre.

Tout ceci correspond à une classe Noeud.java, une classe Arbre.java et le programme d'exemple EssaiArbres.java construit deux arbres différents. Le programme d'exemple construit "à la main" deux arbres pour vous permettre de faire vos premiers tests. Par la suite, la construction d'un arbre se fera par insertion dans un arbre existant.

Enfin, nous dirons qu'un arbre a contient un noeud x si x est la racine de a ou si l'un des fils de la racine de a contient x.
Nous définissons :

une branche comme un couple de noeuds (x,y) tel que y est soit fils gauche de x soit fils droit de x. On dit que x est l'origine de la branche et y sa destination
un chemin vers un noeud x comme une séquence de branches telle que la première branche a pour origine la racine et telle que pour toute paire de branches successives la destination de la première est origine de la seconde
la hauteur d'un noeud x comme le nombre de branches d'un chemin vers x plus 1 (autrement dit, le nombre de noeuds rencontrés sur un chemin vers x)
la hauteur d'un arbre comme le maximum des hauteurs de l'ensemble des noeuds qu'il contient
le nombre de noeuds d'un arbre comme le cardinal de l'ensemble des noeuds qu'il contient

Questions Pour toutes les questions où il vous est demandé d'écrire une méthode, une version récursive (sur les noeuds) sera plus simple et plus naturelle. La solution complète sera alors une méthode d'Arbre qui appelle la méthode récursive sur sa racine.

quel est le nombre de noeuds des arbres du programme donné en exemple ? Leur hauteur ?
écrivez une méthode pour calculer le nombre de noeuds d'un arbre
écrivez une méthode pour calculer la hauteur d'un arbre
écrivez une méthode renvoyant une chaine de caractères représentant un arbre. Vous pouvez :
- commencer par une version "facile" qui représente un arbre comme un triplet avec ses parenthèses et ses virgules
- éventuellement proposer une version plus élaborée qui représente l'arbre avec un noeud par ligne et indente chaque ligne avec un nombre d'espaces dépendant de la hauteur du noeud

2 - Arbres binaires de recherche

Une arbre binaire étiqueté est dit arbre binaire de recherche (ou ABR) si :

son fils gauche et son fils droit son tous les deux des arbres binaires de recherche
son étiquette a une valeur :
- supérieure ou égale à la valeur de chaque étiquettes de son sous arbre gauche
- inférieure ou égale à la valeur de chaque étiquettes de son sous arbre droit

Questions

les deux exemples dans le programme précédent sont-ils des ABR ?
écrivez une méthode permettant de déterminer si une étiquette donnée est présente sur l'un des noeuds d'un ABR
écrivez une méthode permettant d'insérer un nouveau noeud muni d'une étiquette donnée dans un ABR
comment s'y prend-on pour afficher toutes les étiquettes contenues dans un ABR dans l'ordre ?
reprenez la classe ExempleTableau.java utilisée lors du TP sur les tableaux pour générer un tableau d'entiers aléatoires, insérez tous ces entiers dans un ABR et affichez les dans l'ordre.