Structures hiérarchiques et parcours d'arbres

📋 Plan du Cours

1. Définition arbre
2. Nœuds et racine
3. Feuilles et nœuds internes
4. Arbre binaire
5. Profondeur et hauteur
6. Sous-arbre enraciné
7. Inégalités hauteur/nœuds
8. Transformation en arbre binaire
9. Arbres en informatique
10. Parcours en profondeur
11. Parcours en largeur
12. Complexité tri par comparaison

📖 1. Définition arbre

🔑 Notions clés & Définitions

• Arbre (A) : Ensemble non vide muni d’une relation binaire R vérifiant l’unicité de la racine et la relation de parenté.
  Définition : Un arbre est un ensemble non vide où il existe un unique élément racine r tel que tout autre élément x est relié à r via une chaîne de relations parent-enfant.

• Racine (r) : Élément de l’arbre qui n’a pas de parent.
  Point essentiel : La racine est le point de départ de toutes les relations dans l’arbre.

• Nœud (ou sommet) : Élément de l’arbre, pouvant être une feuille ou un nœud interne.
  Définition : Un nœud est un élément de l’arbre, avec une arité correspondant au nombre de ses fils.

• Feuille : Nœud sans fils, de arité 0.
  Point clé : Les feuilles représentent les extrémités de l’arbre, souvent des éléments terminaux.

• Nœud interne : Nœud avec au moins un fils, arité ≥ 1.
  Point essentiel : Ces nœuds permettent de relier différentes parties de l’arbre et de structurer l’information.