Exercices - Parcours d'arbres binaires¶

Il existe plusieurs façons de parcourir un arbre binaire (c'est-à-dire de visiter les nœuds de l'arbre dans un ordre précis), et notamment deux types de parcours :

le parcours en largeur d'abord,
le parcours en profondeur d'abord.

Parcours en profondeur¶

En l’occurrence, trois cas particuliers du parcours en profondeur sont à connaître sur les arbres binaires : le parcours en ordre préfixe, en ordre infixe et en ordre suffixe (ou postfixe).

Ces parcours se définissent de manière récursive. Ils consistent à traiter la racine de l'arbre et à parcourir récursivement les sous-arbres gauche et droit de la racine. Les parcours préfixe, infixe et suffixe se distinguent par l'ordre dans lequel sont effectués ces traitements.

Parcours préfixe, infixe, postfixe¶

Voici un arbre binaire :

Déroulement parcours préfixe

Précondition : L'arbre n'est pas vide
Le parcours préfixe se déroule comme suit :

On visite le nœud racine de l'arbre.
On effectue le parcours préfixe du sous-arbre gauche (s'il est NON vide).
On effectue le parcours préfixe du sous-arbre droit (s'il est NON vide).

Exercice 1

En suivant le déroulement précédent, listez les valeurs des nœuds de l'arbre en figure 1 visités dans l'ordre préfixe.

Déroulement parcours suffixe

Précondition : L'arbre n'est pas vide
Le parcours suffixe se déroule comme suit :

On effectue le parcours suffixe du sous-arbre gauche (s'il est NON vide).
On effectue le parcours suffixe du sous-arbre droit (s'il est NON vide).
On visite le nœud racine de l'arbre.

Exercice 2

En suivant le déroulement précédent, listez les valeurs des nœuds de l'arbre en figure 1 visités dans l'ordre suffixe.

Déroulement parcours infixe

Précondition : L'arbre n'est pas vide
Le parcours infixe se déroule comme suit :

On effectue le parcours infixe du sous-arbre gauche (s'il est NON vide).
On visite le nœud racine de l'arbre.
On effectue le parcours infixe du sous-arbre droit (s'il est NON vide).

Exercice 3

En suivant le déroulement précédent, listez les valeurs des nœuds de l'arbre en figure 1 visités dans l'ordre infixe.

Exercice 4

Redessinez l'arbre en figure 1 en y ajoutant les nœuds vides (notés \(\emptyset\)) et les arêtes associées. Vous pouvez les dessiner en pointillés.
Tracez le contour de l'arbre (en commençant à gauche de la racine).
Listez les nœuds de l'arbre de trois manière différentes :
- Une première liste dans laquelle vous ajoutez chaque nœud lorsque vous passez à sa gauche. Quel est l'ordre de parcours (préfixe, infixe, postfixe) ainsi obtenu ?
- Une seconde liste dans laquelle vous ajoutez chaque nœud lorsque vous passez à sa droite. Quel est l'ordre de parcours (préfixe, infixe, postfixe) ainsi obtenu ?
- Une troisième liste dans laquelle vous ajoutez chaque nœud lorsque vous passez en dessous. Quel est l'ordre de parcours (préfixe, infixe, postfixe) ainsi obtenu ?

Parcours en largeur¶

Le parcours en largeur consiste à parcourir un arbre niveau par niveau. Le nœud de profondeur 0 (ou 1 selon la convention choisie) est d'abord parcouru, puis les nœuds de profondeur 1 (ou 2), et ainsi de suite. À chaque niveau, les nœuds sont parcourus de la gauche vers la droite.

Déroulement parcours en largeur

Le parcours en largeur fonctionne donc de la manière suivante :

On visite le nœud racine
On visite les nœuds fils du nœud racine (d'abord le fils gauche, puis le fils droit)
Puis on visite les nœuds fils du fils gauche du nœud racine, puis les nœuds fils du fils droit du nœud racine
Et ainsi de suite...

Par exemple, si l'on parcourt l'arbre suivant en largeur, les nœuds seront visités dans cet ordre : [E, B, G, A, D, F, H, C]

Parcours en largeur

Exercice 5

Listez les valeurs des nœuds de l'arbre en figure 1 visités lors d'un parcours en largeur.

Exercice 6

Si l'on implémentait l'algorithme de parcours en largeur, on aurait besoin d'une structure de données permettant d'y stocker à chaque fois les prochains nœuds à visiter (qui contiendrait initialement la racine de l'arbre), de manière à ce que le premier nœud ajouté soit le premier nœud visité.

À votre avis, quelle structure de données linéaire pourrait-on utiliser pour implémenter le parcours en largeur ?