Utiliser Python pour déterminer les mesures des arbres binaires
- Fiche de cours
- Quiz
- Profs en ligne
- Videos
- Application mobile
- Utiliser Python pour déterminer la taille d’un arbre binaire.
- Utiliser Python pour déterminer la hauteur d’un arbre binaire.
- La taille et la hauteur d’un arbre binaire se calculent récursivement.
- La taille et la hauteur d’un arbre binaire vide valent 0.
- La taille d’un arbre binaire non vide vaut :
1 + taille(sous-arbre gauche) + taille(sous-arbre droit).
- La hauteur d’un arbre binaire non vide
vaut :
1 + max(hauteur(sous-arbre gauche), hauteur(sous-arbre droit)).
- Comprendre la structure hiérarchique et le vocabulaire des arbres binaires.
- Étudier et implémenter un arbre binaire.
- Utiliser la récursivité en Python.
Pour la calculer, on peut utiliser la représentation récursive des arbres binaires.
- soit vide : sa taille sera égale à 0.
- soit non vide : dans ce cas,
a sera
composé de sa racine, de son
sous-arbre gauche et de son sous-arbre
droit.
Sa taille sera donc :1 + taille(sous-arbre gauche) + taille(sous-arbre droit)
Voici ci-dessous un algorithme de la fonction récursive de calcul de la taille d’un arbre binaire a.
Algorithme | Explication |
Fonction taille(AB a): | On définit la fonction taille qui prend pour paramètre un arbre binaire a de type AB (arbre binaire). |
Si est_vide(a), alors retourner 0 |
Si a est vide, on retourne 0. |
Sinon, retourner 1 + taille(sag(a)) + taille(sad(a)) |
Sinon on retourne la somme de 1 (racine), de la taille de son sous-arbre gauche et de la taille de son sous-arbre droit. |
FinSi | Fin de l’instruction conditionnelle |
est_vide(a) vaut ici Vrai si a est vide et Faux sinon.
sag(a) représente le sous-arbre gauche de a et sad(a) représente son sous-arbre droit.
En Python, la fonction taille(arbre) implémente le calcul de la taille de l’arbre arbre.
Python | Explication |
def taille(arbre): | On définit la fonction taille. |
if arbre.est_vide(): | Si l’arbre est vide, |
return 0 | retourner 0, |
else: | Sinon |
return 1 + taille(arbre.sag) + taille(arbre.sad) |
retourner la somme de 1, de la taille de son sous-arbre gauche et de la taille de son sous-arbre droit. |
On considère l’arbre binaire suivant.
taille(a) renvoie bien 6 (il y a 6 nœuds).
Pour la calculer, on utilise la représentation récursive des arbres binaires.
- soit vide : sa hauteur sera égale à 0 ;
- soit non vide : dans ce cas, la racine de
a correspond à 1 niveau. Il
suffit ensuite d’ajouter le maximum de la
hauteur de ses sous-arbres.
Sa hauteur sera donc :
1 + max(hauteur(sous-arbre gauche), hauteur(sous-arbre droit))
Voici ci-dessous un algorithme de la fonction récursive du calcul de la hauteur d’un arbre binaire a.
Algorithme | Explication |
Fonction hauteur(AB a) : | On définit la fonction hauteur qui prend pour paramètre un arbre binaire a de type AB (arbre binaire). |
Si est_vide(a), alors retourner 0 |
Si a est vide, on retourne 0. |
Sinon, retourner 1 + max(hauteur(sag(a)), hauteur(sad(a))) |
Sinon on retourne la somme de 1 (racine) et du maximum de la hauteur de son sous-arbre gauche et de la hauteur de son sous-arbre droit. |
FinSi | Fin de l’instruction conditionnelle |
En Python, la fonction hauteur(arbre) implémente le calcul de la taille de l’arbre arbre.
Python | Explication |
def hauteur(arbre): | On définit la fonction hauteur |
if arbre.est_vide(): | Si l’arbre est vide, |
return 0 | retourner 0, |
else: | Sinon |
return 1 + max(hauteur(arbre.sag), hauteur(arbre.sad)) |
retourner la somme de 1 et du maximum de la hauteur de son sous-arbre gauche et de la hauteur de son sous-arbre droit. |
On considère l’arbre binaire suivant.
hauteur(a) renvoie bien 4 (il y a 4 niveaux).
Sa taille sera 2h – 1.
On étudie l’arbre binaire suivant.
- La hauteur de cet arbre complet est
h = 3 et il a
bien :
2h –1 = 23 – 1 = 4 feuilles. - La taille de cet arbre est bien 2h – 1 = 23 – 1 = 7.
Vous avez obtenu75%de bonnes réponses !