Arbre binaire ordonné strictement complet de hauteur 3
3. Parcours d’un arbre
Pour la suite, la structure d’un noeud d’un arbre sera la suivante, étant bien compris qu’à chaque noeud est associée
une valeur (sinon l’arbre n’a aucun intérêt) et que bien que cette structure ressemble à celle d’un élément de liste
doublement chaînée ce n’est plus pour une représentation linéaire mais hiérarchique.
Structure noeud
valeur:entier
pGauche:pointeur sur noeud
pDroit:pointeur sur noeud
FinStruct
Chaque arbre binaire peut être décomposé en sousarbres, un à gauche et un à droite. Mais bien souvent un sousarbre peut luimême être éclaté : chaque noeud ayant un ou des fils, contient un ou deux sousarbres, un à droite et
un à gauche. Le noeud 9 a deux sousarbres : un à gauche vers le noeud 9, un à droite vers le noeud 10. Dans les
fonctions de parcours suivantes, à chaque appel chaque noeud ne valant pas NIL est considéré comme la racine d’un
arbre et les sousarbres partant de ce noeud seront parcourus comme tels.
Le parcours complet d’un arbre consiste à parcourir tout l’arbre afin d’accéder l’ensemble des noeuds de l’arbre. Bien
qu’il soit possible de faire ceci avec des structures itératives le moyen le plus facile est d’employer des sousprogrammes récursifs afin de traiter :
q La racine
q Le sousarbre gauche
q Le sousarbre droit
Ce type de parcours est dit préfixé. Le programme va d’abord traiter tous les éléments de gauche. Arrivé à une feuille,
il remonte au noeud précédent, puis passe à droite pour traiter les éléments de gauche de celuici, puis remonte, et
ainsi de suite.
Dans l’arbre binaire de l’exemple, l’ordre de sortie est le suivant :
q Branche gauche : 12 > 9 > 8 (c’est une feuille)
q On remonte au noeud 9
- 3 -
© ENI Editions - All rigths reserved - Jonifar lina
189
3. Parcours d’un arbre
Pour la suite, la structure d’un noeud d’un arbre sera la suivante, étant bien compris qu’à chaque noeud est associée
une valeur (sinon l’arbre n’a aucun intérêt) et que bien que cette structure ressemble à celle d’un élément de liste
doublement chaînée ce n’est plus pour une représentation linéaire mais hiérarchique.
Structure noeud
valeur:entier
pGauche:pointeur sur noeud
pDroit:pointeur sur noeud
FinStruct
Chaque arbre binaire peut être décomposé en sousarbres, un à gauche et un à droite. Mais bien souvent un sousarbre peut luimême être éclaté : chaque noeud ayant un ou des fils, contient un ou deux sousarbres, un à droite et
un à gauche. Le noeud 9 a deux sousarbres : un à gauche vers le noeud 9, un à droite vers le noeud 10. Dans les
fonctions de parcours suivantes, à chaque appel chaque noeud ne valant pas NIL est considéré comme la racine d’un
arbre et les sousarbres partant de ce noeud seront parcourus comme tels.
Le parcours complet d’un arbre consiste à parcourir tout l’arbre afin d’accéder l’ensemble des noeuds de l’arbre. Bien
qu’il soit possible de faire ceci avec des structures itératives le moyen le plus facile est d’employer des sousprogrammes récursifs afin de traiter :
q La racine
q Le sousarbre gauche
q Le sousarbre droit
Ce type de parcours est dit préfixé. Le programme va d’abord traiter tous les éléments de gauche. Arrivé à une feuille,
il remonte au noeud précédent, puis passe à droite pour traiter les éléments de gauche de celuici, puis remonte, et
ainsi de suite.
Dans l’arbre binaire de l’exemple, l’ordre de sortie est le suivant :
q Branche gauche : 12 > 9 > 8 (c’est une feuille)
q On remonte au noeud 9
- 3 -
© ENI Editions - All rigths reserved - Jonifar lina
189