Les arbres
1. Principe
Note : L’implémentation des arbres en Java reprend des principes quasiidentiques aux listes vues
précédemment. Le code Java ne vous sera pas fourni ce coupci ! À 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 ellesmê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 sousprogrammes, 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 de vous (1), vous
placez tout d’abord vos parents (2), puis les parents de vos parents (4), puis les parents de ces derniers (8) et ainsi de
suite. Tous sont reliés par leurs liens de parenté : vous avec vos parents, parents avec grandsparents et ainsi de
suite. Le schéma part de vous, mais pourrait partir de vos arrières grandsparents, ayant x enfants, y petitsenfants, z
arrièrespetits enfants (dont vous), chaque individu étant le successeur de son parent, et le prédécesseur de ses
enfants.
Un arbre généalogique est un arbre binaire
Comment représenter un tel arbre généalogique en programmation ? Vous disposez comme souvent de plusieurs
moyens, notamment avec les bases de données, mais connaissant les listes chaînées, vous devez penser qu’il existe
un moyen ou un autre de s’en sortir directement avec quelques enregistrements et pointeurs. Vous avez raison.
Dans un arbre, chaque élément (membre de votre famille) dispose d’un père et d’une mère, qui ont euxmêmes deux
parents. Un élément peut donc être décrit par plusieurs informations mais deux seulement vont vous intéresser pour la
suite : un élément individu pointe sur son père et sa mère. Un type structuré pouvant représenter un individu pourrait
donc être :
Structure individu
nom:chaîne
pnom :chaîne
...
pPère:pointeur sur individu
pMère:pointeur sur individu
FinStruct
Contrairement aux listes chaînées simples ou doubles, il ne s’agit pas ici de définir une liste, file ou pile mais une notion
de hiérarchie entre éléments pères et fils. Cette hiérarchie porte le nom d’arbre.
2. Définitions
a. Base
- 1 -
© ENI Editions - All rigths reserved - Jonifar lina
187
1. Principe
Note : L’implémentation des arbres en Java reprend des principes quasiidentiques aux listes vues
précédemment. Le code Java ne vous sera pas fourni ce coupci ! À 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 ellesmê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 sousprogrammes, 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 de vous (1), vous
placez tout d’abord vos parents (2), puis les parents de vos parents (4), puis les parents de ces derniers (8) et ainsi de
suite. Tous sont reliés par leurs liens de parenté : vous avec vos parents, parents avec grandsparents et ainsi de
suite. Le schéma part de vous, mais pourrait partir de vos arrières grandsparents, ayant x enfants, y petitsenfants, z
arrièrespetits enfants (dont vous), chaque individu étant le successeur de son parent, et le prédécesseur de ses
enfants.
Un arbre généalogique est un arbre binaire
Comment représenter un tel arbre généalogique en programmation ? Vous disposez comme souvent de plusieurs
moyens, notamment avec les bases de données, mais connaissant les listes chaînées, vous devez penser qu’il existe
un moyen ou un autre de s’en sortir directement avec quelques enregistrements et pointeurs. Vous avez raison.
Dans un arbre, chaque élément (membre de votre famille) dispose d’un père et d’une mère, qui ont euxmêmes deux
parents. Un élément peut donc être décrit par plusieurs informations mais deux seulement vont vous intéresser pour la
suite : un élément individu pointe sur son père et sa mère. Un type structuré pouvant représenter un individu pourrait
donc être :
Structure individu
nom:chaîne
pnom :chaîne
...
pPère:pointeur sur individu
pMère:pointeur sur individu
FinStruct
Contrairement aux listes chaînées simples ou doubles, il ne s’agit pas ici de définir une liste, file ou pile mais une notion
de hiérarchie entre éléments pères et fils. Cette hiérarchie porte le nom d’arbre.
2. Définitions
a. Base
- 1 -
© ENI Editions - All rigths reserved - Jonifar lina
187