Chapitre 5 : Les arbres.
Introduction :
Comment votre ordinateur range-t-il des dossiers dans des sous-dossiers ?
Derrière ces situations se cache une même manière d'organiser l'information : non plus alignée comme une liste, mais répartie sur plusieurs niveaux.
1. Définition
Un arbre est une structure de données qui est hiérarchique, qui peut être non linéaire, dynamique ou non.
Un arbre est composé de noeuds. Le noeud principal est appelé la racine et il est au sommet de la hiérarchie.
Un noeud peut avoir "des enfants" qui sont d'autres noeuds.
2. Exemple
Dans l'exemple ci-dessus :
- John est la racine.
- John a trois enfants.
3. Définition
- Une feuille est un noeud sans enfant.
- La taille d'un arbre correspond à son nombre de noeuds.
- La hauteur d'un arbre correspond à la distance la plus longue entre une racine et une feuille. Cette définition est ambigüe et on a besoin de savoir si l'on compte les arêtes ou les noeuds.
- Son arité correspond au nombre maximal d'enfants que possède un noeud.
4. Exemple
En reprenant l'arbre de l'exemple 2 :
- Quinn est une feuille.
- La taille de l'arbre est de 16.
- La hauteur de l'arbre est égale à 5 si l'on compte les noeuds.
- Son arité est de 4.
5. Exercice : hauteur, taille, arité et parenté d'un arbre.
À faire dans le cahier.
On considère l'arbre suivant :
En partant du principe qu'un arbre composé uniquement d'un seul noeud a une hauteur de 1 :
- Quelle est sa racine ?
- Quelle est sa hauteur ?
- Quelle est sa taille ?
- Quelle est son arité ?
- Combien a-t-il de feuilles ?
- Qui est le grand-parent de Victor ?
- Ian a-t-il des frères/soeurs ?