Arbre

Publié : 29/11/2015 · Modifié : 01/12/2015


Table des matières

Introduction

Une famille de lapin, dont le père s'appelle Bob et la mère Alice, ont des enfants, qui a leurs tours auront des enfants, qui se marieront et auront aussi des enfants. Comment organiser cette famille afin de visualiser qui est marié avec qui, qui sont les parents, qui sont les enfants, combien un couple a-t-il d'enfants, etc. ? Vous connaissez sans doute déjà la réponse, dans notre cas on utilisera un arbre généalogique, vous en avez forcément déjà vu et/ou construit, et cette structure devrait vous être familière.

Mais je vais vous présenter une structure de données plus large que l'arbre généalogique, qui permet de répondre à de nombreux autres problèmes et qui possède beaucoup de variantes : l'arbre.

Principe d'un arbre

Un arbre (tree en anglais) est une structure de données permettant de représenter une hiérarchie. Chaque élément d'un arbre est appelé un nœud, et ils peuvent être reliés par des arêtes à plusieurs nœuds enfants qu'on appelle fils (le nœud parent est appelé père, et le premier nœud de l'arbre est la racine, c'est le seul élément ne possédant pas de père). Si le nœud ne possède aucun fils, on parle alors de feuille.

Exemple d'arbre
Exemple d'arbre

La profondeur d'un nœud est le nombre de nœuds le séparant de la racine, et la hauteur d'un arbre est simplement la profondeur maximale de ses nœuds.

Finalement, un arbre peut être vu comme un graphe particulier (c'est-à-dire orienté, acyclique et avec comme contrainte que chaque nœud ne possède pas plus d'un père).

Implémentation

Comme nous avons vu qu'un arbre est un graphe particulier, on peut donc l'implémenter de la même façon, je vous invite donc à lire la partie Implémentation de mon article sur les graphes pour voir et comprendre les différentes possibilités (matrice d'adjacence, liste d'adjacence et liste d'arcs).

Parcourir un arbre

De même, parcourir un arbre revient à parcourir un graphe, on peut donc utiliser les deux algorithmes de parcours de graphe :

Variantes

Un arbre possède énormément de variantes, qui elles même possèdent des sous variantes, c'est ce qui rend cette structure de données si importante à connaître et à maitriser :

Conclusion

L'arbre est donc une structure de données élémentaire (que l'on peut considérer comme un graphe avec des propriétés spécifiques), s'appliquant dans plusieurs domaines et permettant d'implémenter une hiérarchie :