Dans ce TP vous allez écrire une classe pour représenter un arbre binaire de recherche pour les entiers.
Une référence en anglais et une référence en français (parmi bien d'autres) pour vous rafraichir la mémoire sur les arbres binaires de recherche.
Toutes les classes de ce TP seront dans un paquetage fr.unice.abr.
Un Noeud
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 sans paramètre,
- 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,
- 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 ; utilisez 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).
Vous n'êtes pas connecté. Connexion 