• 4 heures
  • Facile

Ce cours est visible gratuitement en ligne.

course.header.alt.is_video

course.header.alt.is_certifying

J'ai tout compris !

Mis à jour le 30/09/2019

Familiarisez-vous avec les arbres

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

Qu’est-ce qu’un arbre binaire ?

Présentation

Vous souvenez-vous des listes chaînées, ces chasses au trésor aux multiples indices ? Maintenant, imaginez que chaque étape contienne deux adresses et non pas une. Si vous deviez le représenter par un schéma, cela ressemblerait étrangement à un arbre. C’est ce que nous appelons un arbre binaire.

Exemple d'arbre binaire
Exemple d’arbre binaire

Comme dans un arbre généalogique, toutes les cellules sont des cellules filles, sauf une qui est la cellule mère. Si l’arbre n’est pas vide, une seule cellule n’a pas de cellule mère et celle-ci est appelée racine de l’arbre. Toute cellule descend de la racine.

Pourquoi l’appeler arbre binaire ? Car chaque cellule mère a 0, 1 ou 2 cellules enfants qui elles-mêmes sont liées à d’autres cellules.

Dans la terminologie des arbres, les cellules sont appelées des nœuds ou des sommets. Un nœud n’ayant pas de fils s’appelle une feuille.

En d’autres termes, un arbre binaire est une structure analogue à une liste chaînée, sauf que chaque cellule possède jusqu’à deux suivants. Par convention, on convient d’appeler fils gauche et fils droit les deux fils d’un nœud. Le fils gauche et le fils droit d’un nœud peuvent ne pas exister (pointeur égal à NULL). L’accès à l’arbre est donné par un pointeur qui contient l’adresse de la racine.

Parcours d’arbres binaires

Pour trouver une information dans un arbre binaire, il vous faut parcourir tous ses nœuds. Comment faire ? Le moyen le plus simple est de réaliser une fonction récursive.

Une fonction quoi ? J’ai l’impression que tu me laisses là au bord d’un abîme rempli de ptérodactyles affamés. 

Pardon cher lecteur ou chère lectrice ! Nous parlerons de la récursivité un peu plus tard, dans la dernière partie de ce cours. Je vous promets que vous aurez alors toutes les cartes en main pour vous construire un avion et planter là les dinosaures (je sais, je pars un peu loin :-° ).

Il existe de nombreuses manières de parcourir un arbre selon l’ordre dans lequel vous souhaitez examiner les nœuds.

Qu’est-ce qu’un graphe ?

Un graphe est un ensemble de cellules reliées les unes aux autres non plus par un lien d’ascendance, comme dans le cas d’un arbre, mais par une relation. Visuellement, il s’agit d’un ensemble de sommets reliés par des arcs.

Exemple de graphe
Exemple de graphe

Un graphe peut représenter un réseau routier, un réseau de transport aérien, un réseau informatique et bien plus encore.

Les graphes sont souvent utilisés par des algorithmes dont le but est de trouver le plus court chemin entre un point A et un point B. Le service que nous connaissons tous qui utilise ce schéma est Google Maps. Facebook utilise également les graphes pour trouver les amis de vos amis et vous les présenter !

Sur Facebook, chaque personne du réseau est représentée par un cercle (appelé sommet). Vos amis sont reliés à vous par des lignes (appelées arcs). Les amis qui pourraient vous intéresser sont ceux qui sont reliés à vos amis par un arc, tout simplement !

Exemple de certificat de réussite
Exemple de certificat de réussite