Chapitre 5 : Les arbres.
Introduction :
L'idée d'un arbre en informatique est simple : c'est une structure de données qui organise les informations sous forme hiérarchique, avec un nœud racine qui se ramifie en sous-nœuds, formant une structure en branches.
1. Définition:
A copier dans le cahier
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:
A copier dans le cahier
- Une feuille est un noeud sans enfant.
- La taille d'un arbre correspond à son nombre de noeud.
- 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'enfant 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
A 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 feuille?
- Qui est le grand-parent de Victor?
- Ian a-t-il des frères/soeurs?