Deug MASS 2
U.N.S.A.
ALGORITHMIQUE ET STRUCTURES DE DONNEES
TP 11
Arbres binaires et arbres binaires de
recherche
Le but de ce TP est d'apprendre à programmer les opérations de base
sur les arbres binaires et arbres binaires de recherche. En cas de
difficultés, référez-vous au support de cours sur
les arbres.
Toutes les méthodes que l'on demande d'écrire doivent être placées
dans le fichier Arbre.java que vous pouvez récupérer à l'adresse suivante :
http://www-sop.inria.fr/lemme/personnel/Guillaume.Dufay/MASS2/tp10/Arbre.java
Un arbre binaire est constitué de feuilles et de n
uds internes (qui contiennent
chacun une valeur et deux sous-arbres fils gauche et droit).
- 1.
- Écrire une méthode ParcoursPrefixe qui affiche l'ensemble
des n
uds de l'arbre dans l'ordre préfixe, i.e pour chaque n
ud
- (a)
- Afficher la valeur attachée au n
ud
- (b)
- Appeler récursivement la méthode ParcoursPrefixe sur le
sous-arbre gauche
- (c)
- Appeler récursivement la méthode ParcoursPrefixe sur le
sous-arbre droit
La signature de cette méthode sera :
public void ParcoursPrefixe().
- 2.
- Écrire, de même, deux méthodes ParcoursInfixe et ParcoursPostfixe qui affichent l'ensemble des n
uds de l'arbre
respectivement dans l'ordre infixe, i.e pour chaque n
ud
(fils gauche, valeur, fils droit) et dans l'ordre postfixe (fils gauche, fils droit, valeur).
Leur signature respective est :
public void ParcoursInfixe() et public void
ParcoursPostfixe().
- 3.
- Écrire une méthode récursive arbresEgaux qui détermine
si deux arbres sont égaux.
public static boolean arbresEgaux(Arbre a, Arbre b).
- 4.
- Écrire une méthode de calcul de la profondeur d'un arbre
(distance maximale d'une feuille à la racine).
public static int hauteur(Arbre a).
- 5.
- Facultatif : écrire une méthode qui affiche un arbre selon
parcours en largeur. Vous utiliserez la classe File pour stocker les n
uds non encore traités.
public void ParcoursLargeur().
- 1.
- Écrire une fonction de test qui détermine si un arbre binaire a
bien les propriétés d'un arbre binaire de recherche :
- le fils gauche est un arbre binaire de recherche;
- le fils droit est un arbre binaire de recherche;
-
.
La signature est public static boolean estABR(Arbre a).
- 2.
- Écrire un algorithme efficace de recherche d'un élément dans
l'arbre en utilisant les propriétés des arbres binaires.
public boolean recherche(int value)
- 3.
- Écrire une méthode d'insertion d'un élément dans un arbre. On
parcourt l'arbre jusqu'à trouver la feuille que l'on va remplacer par la valeur à insérer.
public void insertion(int value)
- 4.
- Écrire une méthode de suppression d'un élément dans un arbre
binaire de recherche. La suppression commence par la recherche de
l'élément. Puis :
- si c'est une feuille, on peut l'enlever sans problèmes;
- si c'est un n
ud qui n'a qu'un fils, on le remplace par ce
fils;
- si c'est un n
ud qui a deux fils, on a deux solutions, soit le
remplacer par le n
ud de plus grande valeur dans le sous-arbre
gauche, soit le remplacer par le n
ud de plus petite valeur dans le
sous-arbre droit.
public void suppression(int value)
Guillaume Dufay
2001-05-30