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

1. Arbres binaires

Un arbre binaire est constitué de feuilles et de nuds internes (qui contiennent chacun une valeur et deux sous-arbres fils gauche et droit).

1.1 Parcours des arbres

1.

Écrire une méthode ParcoursPrefixe qui affiche l'ensemble des nuds de l'arbre dans l'ordre préfixe, i.e pour chaque nud

(a)

Afficher la valeur attachée au nud

(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 nuds de l'arbre respectivement dans l'ordre infixe, i.e pour chaque nud (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 nuds non encore traités.
public void ParcoursLargeur().

2. Arbres binaires de recherche

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;
• $valeur(fils gauche)\leq valeur\leq valeur(fils droit)$.

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 nud qui n'a qu'un fils, on le remplace par ce fils;
• si c'est un nud qui a deux fils, on a deux solutions, soit le remplacer par le nud de plus grande valeur dans le sous-arbre gauche, soit le remplacer par le nud de plus petite valeur dans le sous-arbre droit.

public void suppression(int value)