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 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.
On utilisera l'ordre naturel des entiers. Cette classe possède :
- Un constructeur avec un paramètre entier (la valeur de la racine).
Elle contiendra aussi
- 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é faut-il donner à la classe Noeud (vous pouvez modifier cette classe si vous le souhaitez) ?
Test
Écrire une classe TestArbreBinaire qui créé 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).
Parcours des arbres
On voudrait pouvoir parcourir les arbres selon leur ordre.
Faire la modification en conséquences.
Vous n'êtes pas connecté. Connexion 