Vous obtenez la séquence 8 9 10 12 13 14 16. C’est très intéressant : l’arbre binaire donné en exemple n’a pas été
choisi au hasard. Il s’agit d’un arbre binaire ordonné, construit de sorte qu’avec un parcours infixé les valeurs des
différents noeuds sont triées.
Fonction infixe(pNoeud :pointeur sur noeud)
Début
Si pNoeud<>NIL Alors
infixe(pNoeud→pGauche) // sous-arbre gauche
Afficher pNoeud→valeur // racine
infixe(pNoeud→pDroite) // sous-arbre droit
FinSi
Fin
4. Arbre binaire ordonné
a. Principe
Un arbre binaire est ordonné si pour une valeur d’un noeud donné, la valeur du fils de gauche lui est inférieure et la
valeur du fils de droite lui est supérieure.
pGauche→valeur < pEncours→valeur < pDroite→valeur
Imaginez que vous voulez rajouter la valeur 15 dans l’arbre :
q Comparez 15 à la racine 12 : c’est supérieur, direction le noeud de droite.
q Comparez 15 au noeud 14 : c’est supérieur, direction le noeud de droite.
q Comparez 15 au noeud 16 : c’est inférieur, direction le noeud de gauche.
q Il n’y a pas de noeud à gauche : placez 15 dans ce nouveau noeud.
Tous les parcours sont possibles, et le parcours infixé vous donne toutes les valeurs déjà triées.
b. Recherche d’un élément
Pour rechercher un élément, vous avez deux solutions : utiliser une solution itérative ou une solution récursive. En
effet les deux sont possibles et assez simples. Il suffit de comparer la valeur recherchée à la valeur de chaque noeud.
Si elle est inférieure, alors la recherche continue à gauche, sinon elle continue à droite, tant qu’une feuille n’a pas été
atteinte et que la valeur n’a pas été trouvée.
La fonction rech1() prend deux arguments : la valeur recherchée et la racine de l’arbre. Elle retourne un booléen VRAI
si la valeur a été trouvée, FAUX sinon. Elle utilise une simple boucle.
Fonction rech1(vrech :entier, pArbre :pointeur sur noeud) :Booléen
Var
trouve :booléen
pEncours :pointeur sur noeud
Début
pEncours=pArbre
trouve=FAUX
Tant que pEncours<>NIL ET trouve=FAUX Faire
Si pEncours→valeur=vrech Alors
trouve=VRAI
Sinon
Si vrech < pEncours→valeur Alors
pEncours=pEncours→pGauche
Sinon
pEncours=pEncours→pDroite
Finsi
FinSi
FinTantQue
Finfonc
- 5 -
© ENI Editions - All rigths reserved - Jonifar lina
191
choisi au hasard. Il s’agit d’un arbre binaire ordonné, construit de sorte qu’avec un parcours infixé les valeurs des
différents noeuds sont triées.
Fonction infixe(pNoeud :pointeur sur noeud)
Début
Si pNoeud<>NIL Alors
infixe(pNoeud→pGauche) // sous-arbre gauche
Afficher pNoeud→valeur // racine
infixe(pNoeud→pDroite) // sous-arbre droit
FinSi
Fin
4. Arbre binaire ordonné
a. Principe
Un arbre binaire est ordonné si pour une valeur d’un noeud donné, la valeur du fils de gauche lui est inférieure et la
valeur du fils de droite lui est supérieure.
pGauche→valeur < pEncours→valeur < pDroite→valeur
Imaginez que vous voulez rajouter la valeur 15 dans l’arbre :
q Comparez 15 à la racine 12 : c’est supérieur, direction le noeud de droite.
q Comparez 15 au noeud 14 : c’est supérieur, direction le noeud de droite.
q Comparez 15 au noeud 16 : c’est inférieur, direction le noeud de gauche.
q Il n’y a pas de noeud à gauche : placez 15 dans ce nouveau noeud.
Tous les parcours sont possibles, et le parcours infixé vous donne toutes les valeurs déjà triées.
b. Recherche d’un élément
Pour rechercher un élément, vous avez deux solutions : utiliser une solution itérative ou une solution récursive. En
effet les deux sont possibles et assez simples. Il suffit de comparer la valeur recherchée à la valeur de chaque noeud.
Si elle est inférieure, alors la recherche continue à gauche, sinon elle continue à droite, tant qu’une feuille n’a pas été
atteinte et que la valeur n’a pas été trouvée.
La fonction rech1() prend deux arguments : la valeur recherchée et la racine de l’arbre. Elle retourne un booléen VRAI
si la valeur a été trouvée, FAUX sinon. Elle utilise une simple boucle.
Fonction rech1(vrech :entier, pArbre :pointeur sur noeud) :Booléen
Var
trouve :booléen
pEncours :pointeur sur noeud
Début
pEncours=pArbre
trouve=FAUX
Tant que pEncours<>NIL ET trouve=FAUX Faire
Si pEncours→valeur=vrech Alors
trouve=VRAI
Sinon
Si vrech < pEncours→valeur Alors
pEncours=pEncours→pGauche
Sinon
pEncours=pEncours→pDroite
Finsi
FinSi
FinTantQue
Finfonc
- 5 -
© ENI Editions - All rigths reserved - Jonifar lina
191