Programme

Partie structures de données

Contenus

Arbres : structures hiérarchiques.
Arbres binaires : nœuds, racines, feuilles, sous-arbres gauches, sous-arbres droits.

Capacités attendues

Identifier des situations nécessitant une structure de données arborescente.
Évaluer quelques mesures des arbres binaires (taille, encadrement de la hauteur, etc.).

Commentaires

On fait le lien avec la rubrique « algorithmique ».

Partie algorithmique

Contenus

Algorithmes sur les arbres binaires et sur les arbres binaires de recherche.

Capacités attendues

Calculer la taille et la hauteur d’un arbre.
Parcourir un arbre de différentes façons (ordres infixe, préfixe ou suffixe; ordre en largeur d’abord).
Rechercher une clé dans un arbre de recherche, insérer une clé.

Commentaires

Une structure de données récursive adaptée est utilisée.
L’exemple des arbres permet d’illustrer la programmation par classe.
La recherche dans un arbre de recherche équilibré est de coût logarithmique.

Vocabulaire

Représentation

Arbres en général

Pour dessiner des arbres : https://www.yworks.com/yed-live/

Les arbres permettent de représenter des données avec des notions de parenté ou de hiérarchie.

Un arbre est constitué de noeuds. Chaque noeud peut avoir zéro ou un parent et zéro ou plusieurs enfants.

Si un noeud n’a pas de parent, c’est un noeud racine. Si il n’a pas d’enfants, c’est un noeud terminal.

Un arbre est vide si il ne contient aucun noeud.

Le segment reliant 2 noeuds est une arête.

La profondeur d’un noeud est le nombre de noeuds rencontrés en remontant de ce noeud jusqu’à la racine (en comptant le noeud et la racine) => profondeur de la racine = 1,…

La hauteur d’un arbre est le plus grand nombre de noeuds rencontrés en descendant de la racine jusqu’à une feuille (en comptant la feuille et la racine). On peut aussi dire que c’est la plus grande profondeur de l’arbre.

Autre définition que l’on peut rencontrer : on ne compte pas les noeuds, mais les arêtes pour profondeur et hauteur (=> profondeur de la racine = 0, mais ces définitions posent problème avec les arbres vides)

Arbres binaires

Un arbre binaire est un arbre où chaque noeud a au maximum 2 enfants (gauche et droit). Une définition plus précise sera donnée plus tard dans le cours.

Représentation en diagramme

Structure de données

Arbre en général

Pour représenter un arbre, on a besoin d’une structure de donnée pour chaque noeud :

Pour un noeud Node :

créer un noeud Node (avec valeurs optionnelles pour valeur et enfants)
ajouter un enfant : Node.add_child(enfant)
supprimer un enfant : Node.remove_child(enfant)
récupérer la liste des enfants : Node.get_children()
modifier la valeur du noeud : Node.set_value(valeur)
récupérer la valeur du noeud : Noeud.get_value()

On peut éventuellement remplacer les get_xxx et set_xxx par des accès directs à des attributs.

Si on veut enregistrer le parent de chaque noeud en même temps que les enfants, les choses sont plus compliquées pour tenir parents et enfant synchronisés (=> on oublie pour l’instant).

Implémentation

A faire en classe

Arbre binaire

Pour un arbre binaire, on peut utiliser une structure de données un peu différente : on ne considère plus une liste d’enfants, mais deux enfants potentiels par noeud : le noeud enfant de gauche et celui de droite

Implémentation

A faire en classe

Parcours d’un arbre

Algorithme récursif global :

pour un noeud donné (= arbre ou sous-arbre)
éventuellement effectuer une opération avec le noeud
pour chaque enfant de ce noeud, appeler récursivement la fonction de parcours pour cet enfant
- éventuellement en fournissant un ou plusieurs arguments (descente d’information)
- éventuellement en récupérant des informations de retour de cette fonction (remontée d’information)
éventuellement effectuer une opération avec le noeud et les éventuels retours de fonction des enfants
éventuellement retourner une valeur pour la fonction appelante

Descente d’information

pour un noeud donné (= arbre ou sous-arbre)
éventuellement effectuer une opération avec le noeud
pour chaque enfant de ce noeud, appeler récursivement la fonction de parcours pour cet enfant en fournissant un ou plusieurs arguments

Remontée d’information

pour un noeud donné (= arbre ou sous-arbre)
pour chaque enfant de ce noeud, appeler récursivement la fonction de parcours pour cet enfant en récupérant des informations de retour de cette fonction
effectuer une opération avec le noeud et les éventuels retours de fonction des enfants
retourner une valeur pour la fonction appelante

Parcours d’un arbre binaire

Algo général

pour un noeud donné
(éventuellement faire une opération avec le noeud)
appeler récursivement la fonction de parcours avec le noeud gauche
(éventuellement faire une opération avec le noeud)
appeler récursivement la fonction de parcours avec le noeud droit
(éventuellement faire une opération avec le noeud)

Parcours préfixe

pour un noeud donné
faire une opération avec le noeud
appeler récursivement la fonction de parcours avec le noeud gauche
appeler récursivement la fonction de parcours avec le noeud droit

Parcours infixe

pour un noeud donné
appeler récursivement la fonction de parcours avec le noeud gauche
faire une opération avec le noeud
appeler récursivement la fonction de parcours avec le noeud droit

Parcours postfixe

pour un noeud donné
appeler récursivement la fonction de parcours avec le noeud gauche
appeler récursivement la fonction de parcours avec le noeud droit
faire une opération avec le noeud

Descente d’une information dans l’arbre

appeler la fonction de parcours avec un argument

Remontée d’une information de l’arbre

valeur de retour dans la fonction de parcours
récupération de cette valeur en postfixe et renvoi