Sommaire

Les arbres

1. Principe

L’implémentation des arbres en Python reprend des principes quasi-identiques aux listes vues précédemment. Le code Python ne vous sera pas fourni ce coup-ci ! À vous d’implémenter ces algorithmes, ce n’est pas très difficile.

Dans la nature, les végétaux décrivent souvent des structures dites arborescentes. L’exemple le plus évocateur est l’arbre : le tronc se décompose en plusieurs branches, se décomposant elles-mêmes en branches plus petites, et ainsi de suite jusqu’aux extrémités où poussent les feuilles.

Selon le cas, après les tableaux et les listes, vous pouvez vous aussi choisir de représenter l’organisation de vos données sous forme d’arborescence en programmation. La notion d’arborescence est très courante sur votre ordinateur personnel, de nombreuses informations sont représentées, directement ou indirectement sous forme d’arborescence : les dossiers des disques durs, la structure d’une page web, la structure d’un site web, la décomposition de l’exécution d’un programme et de ses appels aux sous-programmes, bref tout ce qui peut incorporer une notion de hiérarchie peut être représenté sous forme d’une arborescence.

L’exemple le plus simple à comprendre est la généalogie. On parle d’arbre généalogique. Partant ...