14 - Algorithmes des arbres binaires
L'Arbre est une structure récursive.
Nous allons nous limiter à l'Arbre Binaire de façon à réaliser un nombre de fonctions récursives permettant de l'explorer.
Logiciel nécessaire pour l'activité : -
Prérequis :
- Données : Arbre et Arbre Binaire
- Algos : Parcours d'Arbres
Evaluation ✎ :
Documents de cours : -
1 - Implémentation d'un Arbre Binaire
L'activité d'aujourd'hui ne traite pas de la façon dont on réalise l'implémentation de notre type abstrait Arbre Binaire.
1er partie de la définition de l'arbre binaire
Un Arbre Binaire est :
- Le noeud mène vers un sous-arbre binaire gauche (potentiellement vide donc)
- Le noeud mène vers un sous-arbre binaire droite (potentiellement vide donc)
La distinction entre gauche et droite est fondamentale : placer un noeud à gauche plutôt qu'à droite doit être dû à une raison précise puisqu'il s'agit d'une arbre binaire et pas d'un arbre enraciné d'arité 2.
Réflexion pour obtenir une implémentation SIMPLE sous forme d'objets d'un Arbre Binaire en Python
Vision simple de l'Arbre Binaire
On peut se rendre compte que dans le cadre d'une implémentation la plus basique qui soit :
- Un Arbre Binaire VIDE est un cas particulier.
- Un Arbre Binaire NON VIDE est juste un pointeur vers un noeud.
- Un Noeud est l'association de sa valeur stockée, et des deux sous-arbres binaires auquels il peut mener : vide ou un autre noeud.
Vision simple de la liste chaînée
On retrouve donc la situation déjà rencontrée avec la liste chaînée sous forme de tuple :
- Une liste VIDE est un cas particulier.
- Une liste NON VIDE est juste un pointeur vers la cellule de tête
- Une Cellule est l'association d'une valeur stockée et de son successeur : None ou une autre cellule.
Pour une liste chaînée NON VIDE, nous avions ceci :

On pourait donc écrire ceci :
>>> lst1 = c
Vision simple de l'arbre binaire
Nous allons faire la même chose avec les Arbres Binaires en réalisant une implémentation qui ne distingue pas en réalité l'Arbre Binaire NON VIDE et le Noeud-racine.
Un Arbre Binaire sera une instance de la classe AB contenant trois attributs nommés v pour valeur liée à la racine, g pour sous-arbre gauche et d pour sous-arbre droite.
Un Arbre Binaire VIDE aura alors des attributs None, None, None.
Un Arbre Binaire NON VIDE aura des attributs correspondant à la valeur stockée par sa racine, à son sous-arbre binaire gauche et à son sous-arbre binaire droite.
On choisit donc de ne pas implémenter directement les Noeuds, même si vous allez voir que l'utilisateur ne peut pas le savoir.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41 |
|
01° Lire les classes.
- Quel est le seul cas où on a le droit d'envoyer None comme première valeur au constructeur AB() ?
- S'agit-il d'une précondition imposée via une assertion ou juste d'une précondition à suivre mais sans vérification ?
- Que faire pour créer un arbre ne contenant qu'un noeud dont la valeur est 10 ?
...CORRECTION...
Question 1
On ne peut envoyer None qui si on désire créer un Arbre Vide.
Il faut alors utiliser par exemple AB(None, None, None).
D'ailleurs, puisqu'il s'agit des valeurs par défaut, on peut même juste envoyer ceci :
Il faut alors utiliser par exemple AB().
Question 2
Rien n'est vérifié par une assertion ou un test. Il s'agit donc d'une simple indication à suivre scrupuleusement.
Question 3
Pour créer un Arbre ne contenant qu'un noeud-racine, il faut donc utiliser ceci :
Il faut alors utiliser par exemple AB(10, AB(None, None, None), AB(None, None, None))
Ou encore mieux (à cause des valeurs par défaut) AB(10, AB(), AB())
Ou encore mieux (à cause des valeurs par défaut) AB(10)
02° Répondre aux deux questions ci-dessous :
- Ligne 6 : comment se nomment les variables qu'on trouve sur cette ligne : des paramètres ou des attributs ?
- Ligne 17 : comment se nomme le v de self.v ?
...CORRECTION...
03° Répondre aux deux questions ci-dessous :
- Ligne 21 : quel mot de vocabulaire utilisé pour décrire relier_a_gauche() ?
- Ligne 25 : d'après la documentation de relier_a_gauche(), quel doit-être le type du paramètre sous_arbre ?
- Comment pourrait-on imposer cette précondition sur le type du paramètre sous_arbre si on le voulait ?
- Ligne 30 : que fait cette ligne qui est finalement la seule vraie ligne hors documentation de cette méthode ?
- Quel appel faire si on veut que le sous-arbre gauche d'un arbre arbre soit un arbre vide ?
...CORRECTION...
- Méthode
- sous_arbre devrait être une instance de la classe AB.
- On pourrait rajouter l'une de ces lignes en tant que première ligne de la méthode :
- Cette ligne modifie l'attribut gauche en y plaçant la référence de l'arbre qui servira de sous-arbre gauche.
- Il faut taper ceci
assert isinstance(sous_arbre, AB)
assert type(sous_arbre) == AB
arbre.relier_a_gauche(AB(None, None, None)).
Ou
arbre.relier_a_gauche(AB()).
04° A quoi sert la méthode relier_a_droite() ?
...CORRECTION...
2 - Fonctions d'interface
Maintenant que nous savons comment nous avons implémenté notre Arbre Binaire, nous allons pouvoir étudier et réaliser les fonctions d'interface permettant d'implémenter les primitives nécessaires à la manipulation des Arbres Binaires.
2e partie de la définition du type abstrait de données ARBRE BINAIRE : ses primitives
Description des primitives que nous allons utiliser
- nvABV() -> Arbre Binaire VIDE
- nvAB(e:Element, g:Arbre Binaire, d:Arbre Binaire) -> Arbre Binaire NON VIDE
- estABV(arbre:Arbre Binaire) -> bool
- racine(arbre:Arbre Binaire NON VIDE) -> Noeud
- gauche(arbre:Arbre Binaire NON VIDE) -> Arbre
- droite(arbre:Arbre Binaire NON VIDE) -> Arbre
- contenu(noeud:Noeud) -> Element
Crée un nouvel ARBRE BINAIRE vide.
On le note ainsi pour dire nouvelArbreBinaireVide() car c'est trop long.
Crée un nouvel ARBRE BINAIRE dont le noeud-racine porte l'étiquette e et mène vers les sous-arbres binaires g et d transmis.
Prédicat qui répond True si l'arbre binaire est un arbre binaire vide.
On le note ainsi pour dire estArbreBinaireVide() car c'est trop long.
Renvoie le noeud jouant le rôle de la racine pour l'arbre binaire NON VIDE reçu.
Renvoie le sous-arbre binaire gauche de arbre NON VIDE.
Renvoie le sous-arbre binaire droite de arbre NON VIDE.
Renvoie la valeur du Noeud.
05° Créer un fichier nommé arbre_binaire_ifa.py dans un répertoire qu'on nommera algoAB.
📁 algoAB
📄 arbre_binaire_ifa.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87 |
|
06° Lire chaque fonction d'interface et expliquer briévement ce qu'elles réalisent en analysant leur code.
...CORRECTION...
07° Dessiner l'Arbre Binaire créé par le programme de test (les lignes 80 à 87).
...CORRECTION...

08° Modifier le programme pour qu'il réalise plutôt la réalisation de cet arbre ci :

...CORRECTION...
3 - Utilisation du module
Nous allons maintenant réaliser différentes fonctions nous permettant de déterminer les caractéristiques de l'arbre, en utilisant uniquement les fonctions d'interface et sans nous soucier de l'implémentation.
Le mieux est donc de placer notre implémentation et les fonctions d'interface dans un module et de créer nos propres fonctions en utilisant uniquement les fonctions d'interface.
09° Créer un fichier nommé mes_algos.py dans le répertoire algoAB et contenant le programme Python suivant :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44 |
|
Vous devriez donc avoir deux fichiers situés dans le même répertoire.
📁 algoAB
📄 arbre_binaire_ifa.py
📄 mes_algos.py
Et c'est pour cela qu'avec from arbre_binaire_ifa import ... on parvient facilement à retrouver les fonctions situées dans le fichier arbre_binaire_ifa.py.
10° Expliquer pourquoi on peut directement utiliser la fonction nv_AB() alors que la fonction n'est pas dans ce fichier Python ? Que trouve-t-on directement derrière le import ?
...CORRECTION...
On trouve directement le nom de la fonction nv_AB() derrière le import. On a donc directement importer le nom de cette fonction et on peut l'utiliser juste en tapant son nom.
11° Notre programme importe donc la fonction de cette façon :
from arbre_binaire_ifa import nv_AB
Comment lancer l'appel à nv_AB() si les premières lignes proposaient simplement une importation de ce type :
import arbre_binaire_ifa
...CORRECTION...
Cette fois, on importe que le nom du module arbre_binaire_ifa.
Pour utiliser la fonction, il faut donc taper ceci :
arbre_binaire_ifa.nv_AB()
4 - Parcours et autres algorithmes
Parcours Préfixe (sous forme d'une simple exploration qui ne renvoie rien)
La fonction visiter() sera un simple affichage dans la console : on affichera la clé du noeud.
Préfixe car on commence par visiter le noeud actuel avant de faire autre chose.
On affiche donc le noeud racine lui-même avant ses descendants.
Description des ENTREES / SORTIE
ENTREE : Un Arbre Binaire (possiblement Vide)
SORTIE : Rien (sur l'exemple, il s'agit d'une fonction d'affichage sur l'interface utilisateur)
Description de l'algorithme récursif parcours_prefixe(arbre:Arbre)
SI NON estArbreBinaireVide(arbre)
visiter
(racine(arbre))
parcours_prefixe(gauche(arbre))
parcours_prefixe(droite(arbre))
Fin SI
Renvoyer VIDE
Attention, on donne ici l'algorithme, pas l'implémentation Python.
12° Réaliser la fonction correspondante. Lancer les appels sur l'Arbre Binaire du programme.
1 |
|

Vous devriez obtenir la réponse suivante :
A
C
G
H
B
E
F
D
...CORRECTION...
1
2
3
4
5
6 |
|
13° Réaliser la fonction parcours_suffixe(). Ne regardez votre ancienne fonction, tentez de retrouver seul la solution : le jour de l'examen, vous partirez de rien.
1 |
|

Vous devriez obtenir la réponse suivante :
H
G
B
C
D
F
E
A
...CORRECTION...
1
2
3
4
5
6 |
|
14° Réaliser la fonction parcours_infixe(). Ne regardez votre ancienne fonction, tentez de retrouver seul la solution : le jour de l'examen, vous partirez de rien.
1 |
|

Vous devriez obtenir la réponse suivante :
G
H
C
B
A
E
D
F
...CORRECTION...
1
2
3
4
5
6 |
|
15° Réaliser la fonction hauteur(). Elle doit renvoyer la hauteur de l'arbre.
Comme vous le voyez, cette fonction possède un paramètre qui permet de choisir la profondeur d'un arbre binaire vide. Ici, elle est réglée par défaut à 0. La racine aura donc une profondeur de 1.
1 |
|
- Condition d'arrêt : l'arbre est vide.
- Cas de base : on renvoie la hauteur définie pour l'arbre vide
- Cas récursif :
- On renvoie la somme de 1 et du maximum entre hauteur du sous-arbre gauche et hauteur du sous-arbre droite.
On rappellera que pour trouver le maximum entre deux valeurs, on peut comparer mais on peut également utiliser la fonction native max qui renvoie le plus grand des arguments qu'on lui fournit : si a est plus grand que b, max(a, b) renvoie alors a.
Le jour de l'épreuve pratique, vous pouvez utiliser max() uniquement si vous êtes capable de la recréer.
...CORRECTION...
1
2
3
4
5
6 |
|
16° Réaliser la fonction nb_feuilles(). Elle doit renvoyer le nombre de feuilles de l'arbre.
1 |
|
- Condition d'arrêt 1 : l'arbre est vide.
- Cas de base : on renvoie 0
- Condition d'arrêt 2 : les deux sous-arbres de l'arbre sont vides (c'est une feuille !).
- Cas de base : on renvoie 1
- Cas récursif :
- On renvoie la somme de l'appel récursif sur le sous-arbre-gauche et de l'appel récursif sur le sous-arbre droite.
...CORRECTION...
1
2
3
4
5
6
7
8 |
|
17° Variante : votre fonction doit en plus afficher la clé de la feuille lorsqu'il en trouve une.
Sur l'Arbre Binaire de l'exemple, cela donne :
H
B
D
3

18° Réaliser la fonction taille(). Elle doit renvoyer le nombre de noeuds de l'Arbre Binaire.
1 |
|
- Condition d'arrêt 1 : l'arbre est vide.
- Cas de base : on renvoie 0
- Condition d'arrêt 2 : les deux sous-arbres de l'arbre sont vides (c'est une feuille !).
- Cas de base : on renvoie 1
- Cas récursif :
- On renvoie la somme de 1 et de l'appel récursif sur le sous-arbre-gauche et de l'appel récursif sur le sous-arbre droite.
...CORRECTION...
1
2
3
4
5
6
7
8 |
|
19° Réaliser le prédicat est_present(). Cette fonction doit renvoyer True si la clé fournie apparaît bien comme valeur d'un des noeuds de l'Arbre Binaire.
1 |
|
- Condition d'arrêt 1 : l'arbre est vide.
- Cas de base : on renvoie False
- Condition d'arrêt 2 : la clé de la racine a la bonne valeur.
- Cas de base : on renvoie True
- Cas récursif :
- On renvoie le résultat de la recherche sur l'arbre gauche OU de la recherche dans l'arbre droite.
Question subsidiaire : que renvoie un OU s'il l'un des termes est VRAI ?
...CORRECTION...
1
2
3
4
5
6
7
8 |
|
Vous devriez être bien content maintenant et vous rendre compte du parcours personnel réalisé depuis le début de première.
Il est temps de plonger dans le grand bain :
20° Effacer les instructions des fonctions que vous venez de réaliser aujourd'hui et tenter de le recréer en définissant vous même la récursivité.
Pas facile, mais indispensable pour l'évaluation. C'est l'objectif de la prochaine activité.
5 - FAQ
Rien pour le moment
Activité publiée le 10 12 2020
Dernière modification : 10 12 2020
Auteur : ows. h.