Corrections des TD d'Algorithmique et Java L1 S2 2006-2007

NOUVEAU : notes du projet.

N'oubliez pas de cliquer sur le bouton <Actualiser> de votre navigateur pour voir la dernière version des corrections !

Attention, ce sont des propositions de correction, cela veut dire qu'il existe d'autres solutions et que les solutions proposées ici ne sont pas obligatoirement les meilleures ! Il s'agit des corrections qui ont été proposées en TD.

Pour les corrections Java (feuille 1 et 2) il faut copier le fichier TextWindow.class dans le même répertoire que les autres fichiers.
Vous pouvez aussi copier le fichier source Java TextWindow.java dans le même répertoire que les autres fichiers et le compiler sur votre ordinateur.

Feuille 1 (Révisions tableaux)

Feuille 2 (Récursivité)

Feuille 3 (Structures de données : les listes chaînées)

Exercice 1

Définition de la structure de données LC : liste chaînée d'Élément

Type LC {
    Champ info Type Élément
    Champ suivant Type LC
}

Constructeurs

vide : → LC

Sous-programme LC vide ()
Début
    retourner null
Fin

ajouter : LC × Élément → LC

Sous-programme LC ajouter (LC p, Élément e)
Variables q Type LC
Début
    q ← nouveau LC
    q.info ← e
    q.suivant ← p
    retourner q
Fin

Opérateurs

tête : LC → Élément

tête (vide ()) = erreur
tête (ajouter (l, e)) = e

Sous-programme Élément tête (LC p)
Début
    retourner p.info
Fin

reste : LC → LC

reste (vide ()) = erreur
reste (ajouter (l, e)) = l

Sous-programme LC reste (LC p)
Début
    retourner p.suivant
Fin

estVide : LC → Booléen

estVide (vide ()) = vrai
estVide (ajouter (l, e)) = faux

Sous-programme Booléen estVide (LC p)
Début
    retourner p = null
Fin

appartient : LC × Élément → Booléen

appartient (vide (), x) = faux
appartient (ajouter (l, e), x) = vrai si x = e
appartient (ajouter (l, e), x) = appartient (l, x) si x ≠ e

une version itérative :

Sous-programme Booléen appartient (LC p, Élément x)
Début
    TantQue (non estVide (p)) Faire
        Si (tête (p) = x) Alors
	    retourner vrai
	FinSi
    FinTantQue
    retourner faux
Fin

une version récursive :

Sous-programme Booléen appartient (LC p, Élément x)
Début
    Si (estVide (p)) Alors
        retourner faux
    Sinon
        Si (tête (p) = x) Alors
	    retourner vrai
	Sinon
	    retourner appartient (reste (p), x)
	FinSi
    FinSi
Fin

supprimer1oc : LC × Élément → LC

supprimer1oc (vide (), x) = vide ()
supprimer1oc (ajouter (l, e), x) = l si x = e
supprimer1oc (ajouter (l, e), x) = ajouter (supprimer1oc (l, x), e) si x ≠ e

une version itérative :

Sous-programme LC supprimer1oc (LC p, Élément x)
Variables trouvé type Booléen
Variables q type LC
Début
    Si (estVide (p)) Alors
        retourner p
    Sinon
        Si (tête (p) = x) Alors
	    retourner reste (p)
	Sinon
	    trouvé ← faux
	    q ← p
	    TantQue ((non trouvé) et (non estVide (reste (q)))) Faire
	        Si (tête (reste (q)) = x) Alors
		    q.suivant ← reste (reste (q))
		    trouvé ← vrai
		Sinon
		    q ← reste(q)
		FinSi
            FinTantQue
	    retourner p
        FinSi
    FinSi
Fin

L'un des problèmes de la version itérative ci-dessus est que si p1 et p2 sont deux variables de type LC et x est un Élément alors l'instruction
p2 ← supprimer1oc (p1, x)
modifiera également la liste désigné par p1 dans certains cas (quand l'élément à retirer n'est pas le premier de la liste).
Voici une version itérative qui recopie le début de la liste et évite ce problème :

Sous-programme LC supprimer1oc (LC p, Élément x)
Variables trouvé type Booléen
Variables q, r type LC
Début
    Si (estVide (p)) Alors
        retourner p
    Sinon
        Si (tête (p) = x) Alors
	    retourner reste (p)
	Sinon
	    trouvé ← faux
	    r ← nouveau LC
	    r.info ← tête (p)
	    q ← reste (p)
	    p ← r
	    TantQue ((non trouvé) et (non estVide (q))) Faire
	        Si (tête (q) = x) Alors
		    r.suivant ← q.suivant
		    trouvé ← vrai
		Sinon
		    r.suivant ← nouveau LC
		    r ← r.suivant
		    r.info ← tête (q)
		    q ← q.suivant
		FinSi
            FinTantQue
	    Si (non trouvé) Alors
	        r.suivant ← vide ()
	    FinSi
	    retourner p
        FinSi
    FinSi
Fin

une version récursive en recopiant le début de la liste :

Sous-programme LC supprimer1oc (LC p, Élément x)
Début
    Si (estVide (p)) Alors
        retourner p
    Sinon
        Si (tête (p) = x) Alors
	    retourner reste (p)
	Sinon
	    retourner ajouter (supprimer1oc (reste (p), x), tête (p))
	FinSi
    FinSi
Fin

supprimer : LC × Élément → LC

supprimer (vide (), x) = vide ()
supprimer (ajouter (l, e), x) = supprimer (l, x) si x = e
supprimer (ajouter (l, e), x) = ajouter (supprimer (l, x), e) si x ≠ e

une version récursive qui crée une nouvelle liste :

Sous-programme LC supprimer (LC p, Élément x)
Début
    Si (estVide (p)) Alors
        retourner p
    Sinon
        Si (tête (p) = x) Alors
	    retourner supprimer (reste (p), x)
	Sinon
	    retourner ajouter (supprimer (reste (p), x), tête (p))
	FinSi
    FinSi
Fin

Version itérative en modifiant seulement les liens :

Sous-programme LC supprimer (LC p, Élément x)
Variables q type LC
Début
    TantQue ((non EstVide(p)) et (tête (p) = x)) Faire
        p ← reste (p)
    FinTantQue
    Si (non estVide (p)) Alors
	q ← p
	TantQue (non estVide (reste (q))) Faire
	    Si (tête (reste (q)) = x) Alors
	        q.suivant ← reste (reste (q))
	    Sinon
		q ← reste(q)
	    FinSi
        FinTantQue
    FinSi
    retourner p
Fin

Version itérative en créant une nouvelle liste :

Sous-programme LC supprimer (LC p, Élément x)
Variables q, r type LC
Début
    TantQue ((non EstVide(p)) et (tête (p) = x)) Faire
        p ← reste (p)
    FinTantQue
    Si (non estVide (p)) Alors
        r ← nouveau LC
	r.info ← tête (p)
	q ← reste (p)
	p ← r
	TantQue (non estVide (q)) Faire
	    Si (tête (q) ≠ x) Alors
	        r.suivant ← nouveau LC
		r ← r.suivant
		r.info ← tête (q)
	    FinSi
	    q ← q.suivant
        FinTantQue
        r.suivant ← vide ()
    FinSi
    retourner p
Fin

nbÉlément : LC → Entier

nbÉlément (vide ()) = 0
nbÉlément (ajouter (l, e)) = l + nbÉlément (l)
Version itérative :

Sous-programme Entier nbÉlément (LC p)
Variable n type Entier
Début
    n ← 0
    TantQue (non estVide (p)) Faire
        n ← n + 1
	p ← reste (p)
    FinTantQue
    retourner n
Fin

Version récursive :

Sous-programme Entier nbÉlément (LC p)
Début
    Si (estVide (p)) Alors
        retourner 0
    Sinon
        retourner 1 + nbÉlément (reste (p))
    FinSI
Fin

Exercice 2

L'affichage est
32->16->8->4->2->Fin

À la fin, la variable p0 désigne la liste 2, p1 la liste 4,2 et r la liste vide.

Exercice 3

Type LDC {
    Champ info Type Élément
    Champ prec Type LDC
    Champ suiv Type LDC
}

Sous-Programme LDC LCversLDC (LC p)
Variables q, r Type LDC
Début
    Si (estVide (p)) Alors
        retourner null
    Sinon
        q ← nouveau LDC
	r ← q
	q.info ← tête (p)
	q.prec ← null
	p ← reste (p)
	TantQue (non estVide (p)) Faire
            q.suiv ← nouveau LDC
	    q.suiv.prec ← q
	    q ← q.suiv
	    q.info ← tête (p)
	    p ← reste (p)
	FinTantQue
	q.suiv ← null
	retourner r
    FinSi
Fin

Exercice 4

Tri par sélection en échangeant les infos des maillons :

Sous-Programme LC max (LC p)
Variables m Type LC
Début
    m ← p
    p ← reste (p)
    TantQue (non estVide (p)) Faire
        Si (tête (m) < tête (p)) Alors
	    m ← p
	FinSi
        p ← reste (p)
    FinTantQue
    retourner m
Fin

Sous-Programme LC trier (LC p)
Variables q, m Type LC
Variables aux Type Élément
Début
    q ← p
    Si (non estVide (p)) Alors
	TantQue (non estVide (reste(p))) Faire
            m ← max (p)
            aux ← p.info
            p.info ← m.info
            m.info ← aux
	    p ← reste (p)
	FinTantQue
    FinSi
    retourner q
Fin

Tri quickSort par modification des liens entre les maillons :

Sous-Programme LC quickSort (LC p)
Variables pivot, pp, pg, q Type LC
Début
    Si (non estVide (p)) Alors
        /* on prend le premier élément de la liste comme pivot */
        pivot ← p
        p ← reste (p)
        /* on fait la liste des plus petits pp et la liste des plus grands pg */
        pp ← vide ()
        pg ← vide ()
	TantQue (non estVide (p)) Faire
            q ← reste (p)
	    Si (tête (p) < tête (pivot)) Alors
                p.suivant ← pp
                pp ← p
	    Sinon
                p.suivant ← pg
                pg ← p
	    FinSi
            p ← q
	FinTantQue
	/* on trie la liste des plus petits pp et la liste des plus grands pg */
        pp ← quickSort (pp)
        pg ← quickSort (pg)
	/* on met bout à bout la liste pg, le pivot et la liste pp */
        pivot.suivant ← pp
        Si (estVide (pg)) Alors
	    p ← pivot
	Sinon
	    p ← pg
	    TantQue (non estVide (reste (pg))) Faire
	        pg ← reste (pg)
            FinTantQue
	    pg.suivant ← pivot
        FinSi
    FinSi
    retourner p
Fin

Exercice 5

Définition de la structure de données LCirc : liste circulaire d'Élément

On a une première cellule qui contient le nombre d'élément de la liste et un pointeur vers le dernier élément de la liste

On réutilise le type LC pour stocker les éléments de la liste.

Constructeurs

créerLCirc : → LCirc
ajouterLCirc : LCirc × Élément → LCirc

Opérateurs

retirerLCirc : LCirc × Élément → LCirc: retirerLCirc (vide (), e) = vide ()
retirerLCirc (ajouter (l, e1), e2) = retirerLCirc (l, e2) si e1=e2
retirerLCirc (ajouter (l, e1), e2) = ajouterLCirc (retirerLCirc (l, e2), e1) si e1≠e2
videLCirc : LCirc → Booléen: videLCirc (vide ()) = vrai
videLCirc (ajouter (l, e)) = faux

Le type LCirc :

Type LCirc {
    Champ taille Type Entier
    Champ dernier Type LC
}

Les algorithmes :

Sous-programme LCirc créerLCirc ()
Variables lc Type LCirc
Début
    lc ← nouveau LCirc
    lc.taille ← 0
    lc.dernier ← null
    retourner lc
Fin

Attention quand on ajoute, on souhaite que la liste reste triée en ordre croissant.

Sous-programme LCirc ajouterLCirc (LCirc lc, Élément e)
Variables p, q Type LC
Début
    p ← nouveau LC
    p.info ← e
    Si (videLCirc (lc)) Alors
        /* si la liste était vide alors e devient le seul élément de la liste */
        p.suivant ← p
	lc.dernier ← p
    Sinon
        Si (lc.dernier.info ≤ e) Alors
	    /* si e est supérieur ou égal à tous les éléments de la liste, il devient le dernier élément */
	    p.suivant ← lc.dernier.suivant
	    lc.dernier.suivant ← p
	    lc.dernier ← p
	Sinon
	    /* sinon on recherche l'endroit où insérer e puis on l'insère */
            q ← lc.dernier
            TantQue (q.suivant.info < e) Faire
	        q ← q.suivant
	    FinTantQue
	    p.suivant &larr q.suivant
	    q.suivant &larr p
	FinSi
    FinSi
    /* la liste a un élément de plus */
    lc.taille ← lc.taille + 1
    retourner lc
Fin

Pour retirer, on peut utiliser le fait que la liste est triée...

Sous-programme LCirc retirerLCirc (LCirc lc, Élément e)
Variables p, q Type LC
Début
    Si (non videLCirc (lc)) Alors
        Si (e ≤ lc.dernier.info) Alors
	    /* si l'élément à retirer n'est pas plus grand que le dernier élément de la liste */
	    Si (lc.dernier.info = lc.dernier.suivant.info) Alors
	        /* si tous les éléments de la liste sont identiques */
	        Si (lc.dernier.info = e) Alors
		    /* s'il s'agit de l'élément à retirer */
		    lc.dernier = null
		    lc.taille = 0
		FinSi
	    Sinon
	        /* si tous les éléments de la liste ne sont pas identiques */
		/* p va pointer sur l'élément qui précède celui à retirer */
                p ← lc.dernier
                TantQue (p.suivant.info < e) Faire
                    p ← p.suivant
	        FinTantQue
		/* q va pointer sur l'élément qui suit celui à retirer */
		/* et en même temps on décompte les éléments retirés */
                q ← p.suivant
	        TantQue (q.info = e) Faire
	            q ← q.suivant
		    lc.taille ← lc.taille - 1
	        FinTantQue
		/* le suivant de p est maintenant q */
                p.suivant ← q
	        Si (lc.dernier.info = e) Alors
		    /* si l'élément à retirer était le dernier on a un nouveau dernier qui est p */
	            lc.dernier ← p
	        FinSi
            FinSi
        FinSi
    FinSi
    retourner lc
Fin

Sous-programme Booléen videLCirc (LCirc lc)
Début
    retourner lc.taille = 0
Fin

Exercice 8

Type EntierBinaire {
    Champ bit Type Caractère
    Champ suivant Type EntierBinaire
}

Pour vérifier qu'une liste EntierBinaire correspond à la représentation binaire d'un entier naturel, on vérifie que tous ses champs bit sont des '0' ou des '1' :

Sous-programme Booléen vérifier (EntierBinaire e)
Début
    Si (e = null) Alors
        retourner vrai
    Sinon
        Si ((e.bit ≠ '0') et (e.bit ≠ '1')) Alors
	    retourner faux
	Sinon
	    retourner vérifier (e.suivant)
	FinSi
    FinSi
Fin

Pour convertir un EntierBinaire b_i...b_k+1b_kb_k-1...b₀ en Entier on va utiliser un sous-programme récursif convertir2 qui prend en paramètre l'EntierBinaire b_kb_k-1...b₀ et la conversion v de l'EntierBinaire b_i...b_k+1 car :
convertir2 (b_kb_k-1...b₀, v) = convertir2 (b_k-1...b₀, 2 * v + b_k) = convertir2 (b_i...b_k+1b_kb_k-1...b₀, 0)

Sous-programme Entier convertir (EntierBinaire e)
Début
    retourner convertir2 (e, 0)
Fin

Sous-programme Entier convertir2 (EntierBinaire e, Entier v)
Début
    Si (e = null) Alors
        retourner v
    Sinon
        Si (e.bit = '0') Alors
	    retourner convertir2 (e.suivant, 2 * v)
	Sinon
	    retourner convertir2 (e.suivant, 2 * v + 1)
	FinSi
    FinSi
Fin

Feuille 4 (Structures de données : les piles, les files, les arbres)

Exercice 1

Définition de la structure de données Pile d'Élément

Constructeurs

créerPile : → Pile
empiler : Pile × Élément → Pile

Opérateurs

dépiler : Pile → Pile: dépiler (créerPile ()) = erreur
dépiler (empiler (p, e)) = p
sommet : Pile → Élément: sommet (créerPile ()) = erreur
sommet (empiler (p, e)) = e
pileVide : Pile → Booléen: pileVide (créerPile ()) = vrai
pileVide (empiler (p, e)) = faux
hauteur : Pile → Entier: hauteur (créerPile ()) = 0
hauteur (empiler (p, e)) = 1 + hauteur (p)

Implémentation

Type Pile {
    Champ info Type Élément
    Champ lien Type Pile
}

Sous-programme Pile créerPile ()
Début
    retourner null
Fin

Sous-programme Pile empiler (Pile p, Élément e)
Variables q Type Pile
Début
    q ← nouveau Pile
    q.info ← e
    q.lien ← p
    retourner q
Fin

Sous-programme Pile dépiler (Pile p)
Début
    retourner p.lien
Fin

Sous-programme Élément sommet (Pile p)
Début
    retourner p.info
Fin

Sous-programme Booléen pileVide (Pile p)
Début
    retourner p = null
Fin

Une version itérative du sous-programme hauteur :

Sous-programme Entier hauteur (Pile p)
Variables h Type Entier
Début
    h ← 0
    TantQue (non pileVide (p)) Faire
        p ← p.lien
        h ← h + 1
    FinTantQue
    retourner h
Fin

Une version récursive du sous-programme hauteur :

Sous-programme Entier hauteur (Pile p)
Début
    Si (pileVide (p)) Alors
        retourner 0
    Sinon
        retourner 1 + hauteur (dépiler (p))
Fin

Une version itérative du sous-programme affichePile :

Sous-programme affichePile (Pile p)
Début
    TantQue (non pileVide (p)) Faire
        afficher (sommet (p))
        p ← dépiler (p)
    FinTantQue
Fin

Une version récursive du sous-programme affichePile :

Sous-programme affichePile (Pile p)
Début
    Si (non pileVide (p)) Alors
        afficher (sommet (p))
	affichePile (dépiler (p))
    FinSi
Fin

La traduction en Java, avec les classes Maillon et Pile.

Exercice 2

On veut vérifier uniquement que le parenthésage est correct et on va donc ignorer tous les caractères de la chaîne qui ne sont ni parenthèse ni crochet.

Sous-programme Booléen vérifier (ChaînedeCar x)
Variables correct Type Booléen
Variables p Type Pile
Variables i Type Entier
Variables c Type Caractère
début
    correct ← vrai
    p ← créerPile ()
    i ← 0
    TantQue (correct et i < longueur (x)) Faire
        c ← carIndice (x, i)
	Si (c = '(' ou c = '[') Alors
	    p ← empiler (p, c)
	Sinon
	    Si (c = ')') Alors
	        Si (pileVide (p)) Alors
		    correct ← faux
		Sinon
		    correct ← sommet (p) = '('
                    p ← dépiler (p)
                FinSi
	    Sinon
                Si (c = ']') Alors
	            Si (pileVide (p)) Alors
		        correct ← faux
		    Sinon
		        correct ← sommet (p) = '['
                        p ← dépiler (p)
                    FinSi
		FinSi
            Finsi
        FinSi
	i ← i + 1
    FinTantQue
    Si (correct) Alors
        Si (pileVide (p)) Alors
	    afficher ("parenthésage correct")
	Sinon
	    afficher ("non refermée(s) :")
	    affichePile (p)
	    correct ← faux
	FinSi
    Sinon
        afficher (c, "inattendue")
    FinSi
    retourner correct
fin

La traduction en Java : la classe S2F04E02 (pour pouvoir l'utiliser vous avez besoin de la classe Pile du fichier S2F04E01.java).

Exercice 3

La traduction en Java : on réutilise la classe Pile de l'exercice 1 pour les piles de caractères et on définit la classe PileEnt pour les piles d'entiers.

Exercice 4

Définition de la structure de données File d'Élément

Constructeurs

créerFile : → File
enfiler : File × Élément → File

Opérateurs

défiler : File → File: défiler (créerFile ()) = erreur
défiler (enfiler (f, e)) = f si f est vide
défiler (enfiler (f, e)) = enfiler (défiler (f), e) si f n'est pas vide
tête : File → Élément: tête (créerFile ()) = erreur
tête (enfiler (f, e)) = e si f est vide
tête (enfiler (f, e)) = tête (f) si f n'est pas vide
fileVide : File → Booléen: fileVide (créerFile ()) = vrai
fileVide (enfiler (f, e)) = faux
longueur : File → Entier: longueur (créerFile ()) = 0
longueur (enfiler (f, e)) = 1 + longueur (f)
copier : File → File: copier (créerFile ()) = créerFile ()
copier (enfiler (f, e)) = enfiler (copier (f), e)

Implémentation

On peut utiliser, comme pour les Piles, des listes simplement chaînées (dans le style LC) ou, pour avoir un accès rapide au début et à la fin de la File, on peut utliser des listes circulaires (dans le style LCirc). Je donne la correction avec des listes circulaires : la classe File en Java.

Exercice 5

Récursif :

Sous-programme File inverserRec (File f)
Début
    Si (fileVide (f)) Alors
        retourner créerFile ()
    Sinon
        retourner enfiler (inverserRec (défiler (f)), tête (f))
    FinSi
Fin

Itératif avec une Pile :

Sous-programme File inverserIt (File f)
Variable p Type Pile
Début
    p ← créerPile ()
    TantQue (non fileVide (f)) Faire
        p ← empiler (p, tête (f))
	f ← défiler (f)
    FinTantQue
    f ← créerFile ()
    TantQue (non pileVide (p)) Faire
        f ← enfiler (f, sommet (p))
	p ← dépiler (p)
    FinTantQue
    retourner f
Fin

Le programme Java :S2F04E05.

Exercice 6

Définition de la structure de données ABin d'Élément

Constructeurs

créerABin : → ABin
enracinerABin : Élément × ABin × ABin → ABin

Opérateurs

estVideABin : ABin → Booléen: estVideABin (créerABin ()) = vrai
estVideABin (enracinerABin (e, ag, ad)) = faux
racineABin : ABin → Élément: racineABin (créerABin ()) = erreur
racineABin (enracinerABin (e, ag, ad)) = e
gaucheABin : ABin → ABin: gaucheABin (créerABin ()) = erreur
gaucheABin (enracinerABin (e, ag, ad)) = ag
droiteABin : ABin → ABin: droiteABin (créerABin ()) = erreur
droiteABin (enracinerABin (e, ag, ad)) = ad
estFeuilleABin : ABin → Booléen: estFeuilleABin (créerABin ()) = faux
estFeuilleABin (enracinerABin (e, ag, ad)) = estVideABin (ag) et estVideABin (ad)
tailleABin : ABin → Entier: tailleABin (créerABin ()) = 0
tailleABin (enracinerABin (e, ag, ad)) = 1 + tailleABin (ag) + tailleABin (ad)
hauteurABin : ABin → Entier: hauteurABin (créerABin ()) = 0
hauteurABin (enracinerABin (e, ag, ad)) = 1 + max (hauteurABin (ag), hauteurABin (ad))
nbFeuilleABin : ABin → Entier: nbFeuilleABin (créerABin ()) = 0
nbFeuilleABin (enracinerABin (e, ag, ad)) = 1 si estVideABin (ag) et estVideABin (ad)
nbFeuilleABin (enracinerABin (e, ag, ad)) = nbFeuilleABin (ag) + nbFeuilleABin (ad) sinon

Implémentation

type ABin {
    Champ info Type Élément
    Champ filsG Type ABin
    Champ filsD Type ABin
}

Sous-programme ABin créerABin ()
Début
    retourner null
Fin

Sous-programme ABin enracinerABin (Élément e, ABin ag, ABin ad)
Variable a Type ABin
Début
    a ← nouveau ABin
    a.info ← e
    a.filsG ← ag
    a.filsD ← ad
    retourner a
Fin

Sous-programme Booléen estVideABin (ABin a)
Début
    retourner a = null
Fin

Sous-programme Élément racineABin (ABin a)
Début
    retourner a.info
Fin

Sous-programme ABin gaucheABin (ABin a)
Début
    retourner a.filsG
Fin

Sous-programme ABin droiteABin (ABin a)
Début
    retourner a.filsD
Fin

Sous-programme Booléen estFeuilleABin (ABin a)
Début
    Si (estVideABin (a)) Alors
        retourner faux
    Sinon
        retourner estVideABin (gaucheABin (a)) et estVideABin (droiteABin (a))
    FinSi
Fin

Sous-programme Entier tailleABin (ABin a)
Début
    Si (estVideABin (a)) Alors
        retourner 0
    Sinon
        retourner 1 + tailleABin (gaucheABin (a)) + tailleABin (droiteABin (a))
    FinSi
Fin

Sous-programme Entier hauteurABin (ABin a)
Variables hg, hd Type Entier
Début
    Si (estVideABin (a)) Alors
        retourner 0
    Sinon
        hg ← hauteurABin (gaucheABin (a))
        hd ← hauteurABin (droiteABin (a))
        Si (hd < hg) Alors
            retourner 1 + hg
        Sinon
            retourner 1 + hd
        FinSi
    FinSi
Fin

Sous-programme Entier nbFeuilleABin (ABin a)
Début
    Si (estVideABin (a)) Alors
        retourner 0
    Sinon
        Si (estFeuilleABin (a)) Alors
            retourner 1
        Sinon
            retourner nbFeuilleABin (gaucheABin (a)) + nbFeuilleABin (droiteABin (a))
        FinSi
    FinSi
Fin

Le programme Java : S2F04E06.java (attention, cette manière de programmer la classe ABin n'est pas efficace).

Merci d'envoyer vos remarques à