Cette classe représentera un noeud d'un arbre binaire (pas nécessairement d'un arbre binaire de recherche). Un noeud a une valeur (un entier) et peut avoir 2 noeuds fils : le noeud gauche et le noeud droit.

Mettez dans la classe

un constructeur qui prend une valeur en paramètre,
un constructeur qui prend une valeur et les 2 noeuds gauche et droit en paramètres,
les accesseurs pour la valeur et les 2 noeuds gauche et droit,
des modificateurs pour choisir chacun des 2 noeuds gauche et droit (quels modificateurs faut-il utiliser ?),
une méthode toString() qui affiche les valeurs du noeud et les sous-noeuds attachés à ce noeud.

Vous écrirez une classe TestNoeud pour tester votre classe. Testez seulement la création d'un noeud qui contient un noeud fils. Utiliser la méthode toString() pour vérifier que tout marche bien.

Un arbre binaire de recherche

Définition

Un arbre binaire de recherche a un noeud racine. Pour tout noeud de l'arbre

le sous-noeud gauche est la racine d'un arbre qui contient les éléments inférieurs ou égaux à la valeur du noeud ;
le sous-noeud droit est la racine d'un arbre qui contient les éléments supérieurs à la valeur du noeud.

Dans un premier temps on utilisera l'ordre naturel des entiers.

Cette classe contiendra 2 constructeurs de signatures :

Un constructeur sans paramètres privé.
Un constructeur avec un paramètre entier (la valeur de la racine).

Elle contiendra aussi

un champ statique et public qui s'appelle NULL qui représentera l'arbre vide (cf. constructeur privé sans paramètres)
une méthode pour ajouter un élément dans l'arbre ;
une méthode qui indique si un objet appartient à l'arbre ;
une méthode pour afficher tous les éléments de l'arbre dans leur ordre naturel.

Quelle visibilité allez-vous donner à la classe Noeud (vous pouvez modifier cette classe si vous le souhaitez) ?

Test

Écrivez une classe TestArbreBinaire qui crée un arbre binaire. Pour tester avec des entiers, vous pouvez générer un grand nombre d'entiers de façon aléatoire en utilisant la classe java.util.Random et sa méthode nextInt(int).

Ordre

Tel qu'il est fait votre arbre binaire de recherche range les entiers selon leur ordre naturel. On peut aussi vouloir les ranger selon un ordre différent (par exemple, l'ordre inverse).

Quelles sont les modifications à réaliser pour permettre la construction d'arbres binaires de recherche dont les noeuds sont classés sur un ordre (sur les entiers) prédéfini ? Proposer une implantation en Java !

Parcours des arbres

On voudrait pouvoir parcourir les arbres selon leur ordre. Pour cela, on veut que la classe ArbreBinaireRecherche réalise l'interface Iterable<Noeud>.

Faites la modification en conséquences.

Récupéré depuis "http://miageprojet2.unice.fr/index.php?title=User:FredericMallet/Programmation_Orient%C3%A9e_Objet/Les_arbres"