Polytech Info3

Année 2023 – 2024

API — TD — Séance 6 : Arbres binaires et arbres n-aires

Objectifs

À la fin de cette séance, vous devriez être capable de :

— manipuler et concevoir des arbres comme des structures abstraites ;
— réfléchir aux propriétés des arbres ;
— proposer des implémentations d’arbres cohérentes avec les spécifications choisies en utilisant des struc-
tures sous-jacentes adaptées.

On donne un exemple de spécification d’un type abstrait Arbre construit sur un type Élément.

1 ArbreVide { 33 Résultat : un Arbre, renvoie le fils gauche associé à

Données : aucun la racine de A
3 Résultat : un Arbre vide Pré-condition : A non vide
Post-condition : renvoie un Arbre vide 35 }
5 Effet de bord : aucun
} 37 Libérer(A) {
7 Donnée : un Arbre A
NouveauNœud(G,x,D) { 39 Pré-condition : A non vide
9 Données : un Arbre G, un Élément x, un Arbre D Post-condition : la mémoire associée au nœud ra-
Résultat : un Arbre constitué du nœud (G, x, D) cine de A est libérée
11 Effet de bord : un nouveau nœud a été créé 41 Effet de bord : La racine de A est détruite, les fils
} gauche et droit sont inchangés
13 }
EstArbreVide(A) { 43

15 Donnée : un Arbre A InsérerGauche(A,G) {

Résultat : un booléen vrai ssi A est un Arbre vide 45 Donnée-résultat : un Arbre A
17 } Donnée : un Arbre G
47 Pré-condition : A non vide
19 Racine(A) { Post-condition : le fils gauche de A est remplacé par
Donnée : un Arbre A l’Arbre G.
21 Résultat : l’Élément associé à la racine de A 49 Effet de bord : l’Arbre A est modifié, son ancien fils
Pré-condition : A non vide gauche est «détruit»
23 } }
51

25 FilsDroit(A) { InsérerDroit(A,D) {
Donnée : un Arbre A 53 Donnée-résultat : un Arbre A
27 Résultat : un Arbre, renvoie le fils droit associé à la Donnée : un Arbre D
racine de A 55 Pré-condition : A non vide
Pré-condition : A non vide Post-condition : le fils droit de A est remplacé par
29 } l’Arbre D.
57 Effet de bord : l’Arbre A est modifié, son ancien fils
31 FilsGauche(A) { droit est «détruit»
Donnée : un Arbre A }

Exercice 1. Utilisation du type abstrait Arbre

C Q 1. Dessiner un arbre binaire de hauteur 3 comportant 5 feuilles

En n’utilisant que des primitives du type abstrait :

C Q 2. Écrivez une séquence d’instructions permettant de construire l’arbre binaire proposé à la question 1.
C Q 3. Écrivez une fonction qui prend en paramètre un arbre binaire et renvoie le nombre de feuilles de cet
arbre.

C Q 4. Écrivez une fonction qui prend en paramètre un arbre binaire et renvoie la hauteur de cet arbre.

B Q 5. Écrivez une procédure permettant de «supprimer» un arbre entier, en libérant la mémoire de chacun de
ses nœuds.

Comment procéderiez-vous sans récursivité ?

Exercice 2. Implémentation du type abstrait Arbre

B Q 1. Proposez une implémentation du type Arbre à l’aide d’un tableau de taille N alloué statiquement (on
suppose donc ici que le nombre de nœuds de tout arbre binaire sera limité à N). Écrivez le code de chaque
primitive pour cette implémentation.

B Q 2. Proposez maintenant une implémentation du type Arbre à l’aide de cellules mémoires allouées dynami-
quement et chaînées par pointeurs.

On s’intéresse maintenant à l’implémentation d’un type abstrait «Arbre n-aire», en utilisant le type «Arbre
binaire» présenté précédemment.

Un arbre n-aire est ici implémenté comme suit :

— le «fils aîné» d’un nœud n-aire est implémenté par le «fils gauche» du nœud binaire du père ;
— le «frère cadet» d’un nœud n-aire est implémenté par le «fils droit» du nœud binaire du frère précédent.

Exercice 3.

C Q 1. Traduisez l’arbre ci-dessous dans sa représentation binaire :

3 7 9

4 5 6 8

Nous aurons également besoin d’une notion de liste d’arbres : ici nous allons également représenter une
liste par un arbre binaire : le premier élément de la liste se trouve à la racine de l’arbre, et les éléments
suivants sont situés dans son fils droit (qui est inutilisé pour l’instant, regardez votre arbre de la question
précédente pour vous en convaincre).

Il peut sembler confus d’utiliser la même structure sous-jacente (les arbres binaires) pour implémenter
deux types différents, mais il faut se souvenir qu’on utilisera des primitives de manipulation différentes
pour les listes et pour les arbres n-aires, il n’y aura donc pas d’ambiguïté.
C Q 2. Traduisez la liste d’arbres ci-dessous dans sa représentation binaire :

 
3 7
 
 
 
 
 
 4 5 6 ; 8 ; 9 
 
 
 
 
 
 

Exercice 4.

B* Q 4. Implémentez les primitives du type abstrait «arbre n-aire», telles que définies ci-dessous.
Élément : un type
2 Arbre : un type
ListeArbre : un type
4

ArbreVide
6 { Données : aucun
Résultat : un Arbre vide}
8

NouveauNœud
10 { Données : un Élément x, une ListeArbre L
Résultat : un Arbre constitué du nœud x, dont les fils sont les éléments de L
12 Effet de bord : un nouveau nœud a été créé }

14 EstArbreVide
{ Données : un Arbre A
16 Résultat : un booléen vrai ssi A est un Arbre vide }

18 Elem
{ Données : un Arbre A
20 Résultat : l’Élément associé àla racine de A
Pré-condition : A est non vide }
22

ListeFils
24 { Données : un Arbre A
Résultat : une ListeArbre
26 description : A doit être non vide, renvoie la liste des fils associée à la racine de A }

28 { Manipulation des listes d’arbres }

30 ListeVide
{ Données : aucun
32 Résultat : une ListeArbre vide }

34 Cons
{ Données : un Arbre A, une ListeArbre L
36 Résultat : une ListeArbre constituée de l’arbre A, suivi de la liste L. }

38 EstListeVide
{ Données : une ListeArbre L
40 Résultat : un booléen vrai ssi L est vide. }

42 Premier
{ Données : une ListeArbre L
44 Résultat : un Arbre, renvoie le premier arbre de la liste L
Pré-condition : L non vide }
46

Suivants
48 { Données : une ListeArbre L
Résultat : une ListeArbre, renvoie la liste des arbres suivants le premier.
50 Pré-condition : L non vide }