Fiche de cours

Comprendre la structure hiérarchique des arbres binaires

Lycée > Terminale > NSI > Comprendre la structure hiérarchique des arbres binaires

Fiche de cours
Quiz et exercices
Vidéos et podcasts

Objectifs

Comprendre la structure hiérarchique et le vocabulaire des arbres.
Comprendre la structure hiérarchique et le vocabulaire des arbres binaires.

Points clés

Un arbre est une structure hiérarchique constituée de nœuds reliés par des branches.
Chaque nœud, sauf la racine, a un seul père. Chaque nœud, sauf les feuilles, a au moins un fils.
Chaque nœud porte une étiquette, appelée aussi valeur ou clé.
La hauteur ou profondeur d’un arbre est son nombre de niveaux.
La taille d’un arbre est son nombre de nœuds.
Un arbre binaire est un arbre dont chaque nœud a au plus deux fils : un fils gauche et un fils droit.
La taille d’un arbre binaire de hauteur h est comprise entre h et 2^h – 1.

Pour bien comprendre

Connaitre les structures linéaires de liste, pile et file.

1. La structure hiérarchique d'un arbre

a. Définitions

En informatique, les informations sont souvent hiérarchisées. On les représente souvent sous la forme d’une arborescence. Cela permet de stocker des données volumineuses tout en permettant un accès rapide.

Un arbre est une structure hiérarchique constituée de nœuds reliés entre eux par des branches, telle que chaque nœud a un père et un seul, à l’exception d’un nœud appelé racine. Chaque nœud porte une information appelée étiquette, valeur ou clé.

Les feuilles d’un arbre sont les seuls nœuds qui ne sont pères d’aucun autre nœud. Les autres nœuds (y compris la racine) sont des nœuds internes.

Exemple
Un élève a choisi comme enseignements de spécialité la NSI et les mathématiques. On peut représenter dans un arbre les enseignements qu’il suit en terminale générale.

La racine de cet arbre est le nœud étiqueté « Terminale générale ».
Le nœud qui porte la clé « NSI » a pour père le nœud qui porte la clé « Enseignements de spécialité ».
Les feuilles de cet arbre sont les nœuds qui portent des valeurs « LVA », « LVB », « HG », « EPS », « Ens. Scient. », « Philo », « Mathématiques » et « NSI ».

Un sous-arbre d’un arbre est un arbre dont les nœuds et les branches sont des nœuds et des branches de l’arbre d’origine.

Exemple
L’arbre suivant est un sous-arbre de l’arbre de l’exemple précédent.

b. Vocabulaire

Le vocabulaire des arbres est inspiré des liens de parenté.

Un nœud 1 est un fils d’un nœud 2, si le nœud 2 est le père du nœud 1.
Les descendants d’un nœud sont les nœuds de ses sous-arbres. Un descendant d’un nœud est donc soit son fils, soit un descendant de l’un de ses fils.
Un ancêtre d’un nœud est soit son père, soit un ancêtre de son père.
Un frère d’un nœud est un fils de son père qui n’est pas le nœud lui-même.

Exemple

En reprenant l’arbre précédent, le nœud « Mathématiques » est un frère du nœud « NSI ».
Les descendants du nœud « Enseignements communs » sont les nœuds « Langues », « HG », « EPS », « Ens. Scient. », « Philo », « LVA » et « LVB ».
Le nœud « Enseignements communs » est un ancêtre du nœud « LVB ».

c. Mesures dans un arbre

Les nœuds d’un arbre se répartissent par niveaux.

Le niveau 0 contient la racine.
Le niveau 1 contient les fils de la racine.
…
Le niveau k contient les fils des nœuds
du niveau k – 1.

La hauteur ou profondeur d’un arbre est le nombre de niveaux qu’il contient.

La hauteur ou profondeur d’un nœud est le nombre de ses ancêtres.

La taille d’un arbre est le nombre total de nœuds de cet arbre.

Exemple

La taille de l’arbre précédent est 12 car il contient 12 nœuds.
La profondeur de cet arbre est 4 car on y compte 4 niveaux.
La profondeur du nœud « NSI » est 2 car il a 2 ancêtres : « Enseignements de spécialité » et « Terminale Générale ».

2. L'arbre binaire

a. Définitions

Arbre binaire

Un arbre binaire est un arbre dont les nœuds ont au plus deux fils. On parle alors de fils gauche et de fils droit. Dans le cas où un nœud a un seul fils, on parle indifféremment de fils gauche ou de fils droit.

Exemple
L’expression algébrique 3(y – 4) peut être représentée par l’arbre binaire suivant.

En effet, comme les opérateurs × et – sont des opérateurs binaires, on peut les représenter sous la forme de nœuds avec un fils gauche et un fils droit.

L’expression y – 4 est ainsi représentée par l’arbre suivant.

Arbre binaire complet

Un arbre binaire est dit complet si chaque nœud, à l’exception des feuilles, a exactement deux fils.

Exemple
L’expression algébrique (a + 2)(b – 5) peut être représentée par l’arbre binaire suivant.

Cet arbre binaire est complet car ses nœuds internes ×, + et – ont exactement deux fils.

b. Mesures

Comme on connait la totalité de la structure d’un arbre complet, on peut facilement obtenir ses mesures.

Si on considère ses différents niveaux, on peut en effet calculer le nombre de nœuds.

Le niveau 0 contient 1 nœud : 2⁰ nœud.
Le niveau 1 contient 2 nœuds : 2¹ nœuds.
Le niveau 2 contient 4 nœuds : 2² nœuds.
…
Le niveau k contient 2^k nœuds.

Un arbre complet de hauteur h aura 2^h^–¹ feuilles (nœuds qui ne sont pères d’aucun autre nœud).

Sa taille (nombre total de nœuds) sera 2^h – 1.

La taille d’un arbre binaire de hauteur h est comprise entre h (arbre dont chaque nœud a un seul fils) et 2^h – 1 (arbre complet).

Exemple
On étudie l’arbre binaire de l’exemple précédent.

La hauteur de cet arbre complet est h = 3
et il a bien 2^h^–¹= 2^3–1= 4 feuilles.
La taille de cet arbre est bien 2^h – 1 = 2³– 1 = 7.

Évalue ce cours !

Note 5 / 5. Nombre de vote(s) : 2

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