Sommaire

Arbres

1. Généralités sur les arbres

a. Principe

Un arbre est une structure de données qui permet de stocker des informations mais aussi une hiérarchie et une organisation des informations :

images/06ri43.png

L’arbre est constitué de nœuds reliés entre eux de façon hiérarchique par des arêtes. Le premier nœud est appelé racine, les derniers, ceux après lesquels il n’y a plus de nœud sont les feuilles. Un parcours de la racine vers une feuille est une branche. Chaque nœud peut être considéré comme la racine d’un sous-arbre constitué de sa descendance et de lui-même. L’arbre est de ce fait une structure récursive. Dans l’exemple ci-dessus chaque sous-arbre correspond à un parenthésage. Une information parenthésée peut traduire un arbre. L’expression : ( personne( nom, prénom, adresse( numéro, rue, ville, département) ) ) est celle de l’arbre :

images/06ri44.png

Chaque étage de l’arbre est appelé niveau et les niveaux sont numérotés de 1 la racine à n la feuille la plus basse. La hauteur d’un arbre est le niveau maximum atteint par une feuille. La hauteur de l’arbre ci-dessus est 3.

Souvent on parle de nœuds parents et de nœuds fils. Les nœuds fils sont ceux qui descendent d’un nœud parent et seule la racine n’a pas de parent. Dans l’exemple précédent, personne ...