Deug MASS 2  Année 2000/2001

U.N.S.A.

ALGORITHMIQUE ET STRUCTURES DE DONNEES

TP N^{o} 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 nœuds 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 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 sousarbre gauche

(c) Appeler récursivement la méthode ParcoursPrefixe sur le sousarbre 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().

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(filsgauche) ≤ valeur ≤ valeur(filsdroit).

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 sousarbre droit.

public void suppression(int value)