Fiche de cours

Étudier et implémenter un arbre binaire

Lycée > Terminale > NSI > Étudier et implémenter un arbre binaire

Fiche de cours
Quiz et exercices
Vidéos et podcasts

Objectif

Étudier et implémenter un arbre binaire.

Points clés

Un arbre binaire peut être représenté sous la forme d’un triplet (racine ; sous-arbre gauche ; sous-arbre droit).
En Python, les arbres binaires peuvent être implémentés en programmation objet avec une classe.

Pour bien comprendre

Connaitre les structures linéaires de liste, pile et file.
Comprendre la structure hiérarchique des arbres binaires.
Créer une classe en Python.
Utiliser la récursivité.

1. Les arbres binaires comme des triplets

a. Représentation sous la forme d'un triplet

Dans un arbre binaire, chaque nœud peut se définir par sa racine et ses deux sous-arbres : son sous-arbre gauche et son sous-arbre droit.

On peut ainsi représenter un arbre binaire comme un triplet (racine ; sous-arbre gauche ; sous-arbre droit), chaque sous-arbre étant également défini de la même manière.

Le cas des feuilles de l’arbre est particulier puisque ce sont des nœuds sans sous-arbres. On conviendra de les représenter de la manière suivante : (feuille ; () ; ()) où () sont des arbres vides.

Exemple
L’expression algébrique 5a + 8 peut être représentée par l’arbre binaire suivant.

Les feuilles 5 et a peuvent être respectivement représentées par les triplets (5 ; () ; ()) et (a ; () ; ()).

L’expression 5a peut ainsi être représentée par :

(× ; (5 ; () ; ()) ; (a ; () ; ()))

C’est pourquoi on représentera l’expression 5a + 8 par le triplet suivant.

(+ ; (× ; (5 ; () ; ()) ; (a ; () ; ())) ; (8 ; () ; ()))

b. En Python

En Python, les triplets peuvent être créés à partir de tableaux (de type list) imbriqués les uns dans les autres.

Exemple
On considère l’arbre binaire suivant.

En Python, le triplet correspondant est le suivant.

[1, [2, [4, [], []], [5, [], []]], [3, [], [6, [], []]]]

2. La définition récursive des arbres binaires

a. Représentation formelle

La représentation précédente est explicite. Elle donne néanmoins des structures peu lisibles et difficilement utilisables. En s’en inspirant, on peut en donner une version récursive (qui s’appelle elle-même).

Un arbre binaire est une structure de données que l’on peut définir récursivement.

En effet, un arbre binaire est :

soit vide ;
soit composé d’une racine qui porte une étiquette et d’une paire de sous-arbres : son sous-arbre gauche et son sous-arbre droit.

Pour manipuler des arbres binaires, on doit donc disposer des fonctions suivantes :

est_vide(a) : une fonction qui renvoie True si l’arbre binaire a est vide et False sinon ;
creer_arbre_vide() : une fonction qui crée un arbre vide ;
creer_arbre(val, sag, sad) : une fonction qui crée un arbre de racine étiquetée val, de sous-arbre gauche sag et de sous-arbre droit sad.

Il faudra également des fonctions qui retournent l’étiquette de la racine, des sous-arbres gauche et droit, et des fonctions qui les modifient.

b. En Python

En Python, les arbres binaires sont souvent implémentés grâce à des classes. La programmation orientée objet permet ainsi de définir les arbres binaires en tant que structure complète, avec des méthodes intégrées.

On définit ainsi la classe ArbreBinaire.

Python	Explication
class ArbreBinaire:	On définit la classe ArbreBinaire.
def __init__(self, etiquette=None, sag=None, sad=None): self.etiquette=etiquette self.sag=sag self.sad=sad	On définit le constructeur de la classe ArbreBinaire avec trois attributs : etiquette renvoie l’étiquette de l’arbre. sag renvoie le sous-arbre gauche. sad renvoie le sous-arbre droit.
def est_vide(self): if self.etiquette is None: return True else: return False	On définit la méthode est_vide() qui renvoie True si l’arbre est vide et False sinon.

Exemple
On considère l’arbre binaire suivant.

Grâce à la classe précédente, on peut créer cet arbre de la manière suivante.

Python	Explication
a=ArbreBinaire()	On définit l’arbre binaire vide a.
a.etiquette=1	On attribue à l’étiquette de a la valeur 1.
a.sag=ArbreBinaire(2)	On définit le sous-arbre gauche de a comme un arbre d’étiquette 2
a.sad=ArbreBinaire(3)	On définit le sous-arbre droit de a comme un arbre d’étiquette 3.
a.sag.sag=ArbreBinaire(4)	On définit le sous-arbre gauche du sous-arbre gauche de a comme un arbre d’étiquette 4.
a.sag.sad=ArbreBinaire(5)	On définit le sous-arbre droit du sous-arbre gauche de a comme un arbre d’étiquette 5.
a.sad.sag=ArbreBinaire()	On définit le sous-arbre gauche du sous-arbre droit de a comme un arbre vide.
a.sad.sad=ArbreBinaire(6)	On définit le sous-arbre droit du sous-arbre droit de a comme un arbre d’étiquette 6.
a.sag.sag.sag=ArbreBinaire() a.sag.sag.sad=ArbreBinaire()	Comme 4 est une feuille, on définit ses sous-arbres comme des arbres vides.
a.sag.sad.sag=ArbreBinaire() a.sag.sad.sad=ArbreBinaire()	Comme 5 est une feuille, on définit ses sous-arbres comme des arbres vides.
a.sad.sad.sag=ArbreBinaire() a.sad.sad.sad=ArbreBinaire()	Comme 6 est une feuille, on définit ses sous-arbres comme des arbres vides.

Pour accéder à l’étiquette 5, on appelle ainsi l’instruction a.sag.sad.etiquette.

Pour définir les feuilles, on peut directement y mettre les sous-arbres vides.
Pour la feuille 6, il suffirait d’utiliser l’instruction :
a.sad.sad=ArbreBinaire(6, ArbreBinaire(), ArbreBinaire()).

Voici ce code sur Python Tuthor.

Le code crée ici la structure de l’arbre. Les données sont juste stockées de façon hiérarchique. L’arbre permet de les atteindre.

Évalue ce cours !

Note 4 / 5. Nombre de vote(s) : 1

Des quiz et exercices pour mieux assimiler sa leçon

La plateforme de soutien scolaire en ligne myMaxicours propose des quiz et exercices en accompagnement de chaque fiche de cours. Les exercices permettent de vérifier si la leçon est bien comprise ou s’il reste encore des notions à revoir.

S’abonner

Des exercices variés pour ne pas s’ennuyer

Les exercices se déclinent sous toutes leurs formes sur myMaxicours ! Selon la matière et la classe étudiées, retrouvez des dictées, des mots à relier ou encore des phrases à compléter, mais aussi des textes à trous et bien d’autres formats !

Dans les classes de primaire, l’accent est mis sur des exercices illustrés très ludiques pour motiver les plus jeunes.

S’abonner

Des quiz pour une évaluation en direct

Les quiz et exercices permettent d’avoir un retour immédiat sur la bonne compréhension du cours. Une fois toutes les réponses communiquées, le résultat s’affiche à l’écran et permet à l’élève de se situer immédiatement.

myMaxicours offre des solutions efficaces de révision grâce aux fiches de cours et aux exercices associés. L’élève se rassure pour le prochain examen en testant ses connaissances au préalable.

S’abonner

Des vidéos et des podcasts pour apprendre différemment

Certains élèves ont une mémoire visuelle quand d’autres ont plutôt une mémoire auditive. myMaxicours s’adapte à tous les enfants et adolescents pour leur proposer un apprentissage serein et efficace.

Découvrez de nombreuses vidéos et podcasts en complément des fiches de cours et des exercices pour une année scolaire au top !

S’abonner

Des podcasts pour les révisions

La plateforme de soutien scolaire en ligne myMaxicours propose des podcasts de révision pour toutes les classes à examen : troisième, première et terminale.

Les ados peuvent écouter les différents cours afin de mieux les mémoriser en préparation de leurs examens. Des fiches de cours de différentes matières sont disponibles en podcasts ainsi qu’une préparation au grand oral avec de nombreux conseils pratiques.

S’abonner

Des vidéos de cours pour comprendre en image

Des vidéos de cours illustrent les notions principales à retenir et complètent les fiches de cours. De quoi réviser sa prochaine évaluation ou son prochain examen en toute confiance !

S’abonner

Profs en ligne

Découvrez le soutien scolaire en ligne avec myMaxicours

Plongez dans l'univers de myMaxicours et découvrez une approche innovante du soutien scolaire en ligne, conçue pour captiver et éduquer les élèves de CP à la terminale. Notre plateforme se distingue par une riche sélection de contenus interactifs et ludiques, élaborés pour stimuler la concentration et la motivation à travers des parcours d'apprentissage adaptés à chaque tranche d'âge. Chez myMaxicours, nous croyons en une éducation où chaque élève trouve sa place, progresse à son rythme et développe sa confiance en soi dans un environnement bienveillant.

Profitez d'un accès direct à nos Profs en ligne pour une assistance personnalisée, ou explorez nos exercices et corrigés pour renforcer vos connaissances. Notre assistance scolaire en ligne est conçue pour vous accompagner à chaque étape de votre parcours éducatif, tandis que nos vidéos et fiches de cours offrent des explications claires et concises sur une multitude de sujets. Avec myMaxicours, avancez sereinement sur le chemin de la réussite scolaire, armé des meilleurs outils et du soutien de professionnels dédiés à votre épanouissement académique.

EXERCE-TOI EN T'ABONNANT