Ce tri est effectué en répartissant l'information sous forme
d'arbre binaire (chaque noeud ne possède qu'une ou 2 branches). Si
l'élément à placer est plus petit que l'élément
auquel on le compare, on se déplace vers la gauche, sinon, on se
déplace vers la droite. Lorsque on arrive au bout de la branche,
on place l'élément.
Soient les nombres 6 5 4 9 1 7 8 3 2 à trier.
On place 6 à la racine et on esaie de placer 5. Celui-ci est
inférieur à 6.
On le place donc dans le sous-arbre gauche:
6
/
5
On examine ensuite 4. Il est inférieur à 6 et doit donc être
placé à gauche.
On se déplace vers la gauche où on rencontre 5. Comme 4 lui est
inférieur, on se dirige vers la gauche. Comme on arrive en fin de
branche, on place 4 sur la gauche puisqu'il est inférieur à 5.
6
/
5
/
4
Nous plaçons maintenant 9 qui est supérieur à 6. On se dirige
donc vers la droite où on arrive en fin de branche. On place donc le 9.
6
/ \
5 9
/
4
Le nombre suivant à placer est 1. Il est inférieur à 6,
on se dirige vers la gauche où on rencontre 5. 1 lui est inférieur
et on se dirige vers la gauche où on rencontre 4. 1 lui est inférieur
et on se dirige vers la gauche où on place 1 puisqu'il est inférieur à 4.
6
/ \
5 9
/
4
/
1
Le nombre suivant à placer est 7. Il est supérieur à 6,
on se dirige vers la droite où on rencontre 9. 7 lui est inférieur
et on se dirige vers la gauche où on le place puisqu'on est arrivé
en fin de branche.
6
/ \
5 9
/ /
4 7
/
1
Le nombre suivant à placer est 8. Il est supérieur à 6, on se dirige vers
la droite où on rencontre 9. 8 lui est supérieur et on se dirige vers la
droite où on rencontre le 7 qui lui est inférieur. On se dirige vers la
droite où on place 8 puisqu'on est arrivé en fin de branche.
6
/ \
5 9
/ /
4 7
/ \
1 8
Le nombre suivant à placer est 3. Il est inférieur à 6, on se dirige vers
la gauche où on rencontre 5. 3 lui est inférieur et on se dirige vers la
gauche où on rencontre 4. 3 lui est inférieur et on se dirige vers la
gauche où on rencontre 1. 3 lui est supérieur et on se dirige vers la
droite où on place 3 puisqu'on est arrivé en fin de branche.
6
/ \
5 9
/ /
4 7
/ \
1 8
\
3
Le nombre suivant à placer est 2. Il est inférieur à 6, on se dirige vers
la gauche où on rencontre 5. 2 lui est inférieur et on se dirige vers la
gauche où on rencontre 4. 2 lui est inférieur et on se dirige vers la
gauche où on rencontre 1. 2 lui est supérieur et on se dirige vers la
droite où on rencontre 3. 2 lui est inférieur et on se dirige vers la
gauche où on place 2 puisqu'on est arrivé en fin de branche.
6
/ \
5 9
/ /
4 7
/ \
1 8
\
3
/
2
Pour obtenir les éléments triés, on va jusqu'à la feuille la plus à gauche.
On y trouve 1. C'est l'élément le plus petit. On explore maintenant le demi-
arbre droit qui se développe à partir de cet élément et on se déplace jusqu'à
sa feuille la plus à gauche. On y trouve 2. C'est le deuxième élément. On
explore ensuite le demi-arbre droit qui se développe à partir de cet élément.
Il est inexistant. On remonte à la feuille supérieure où on trouve 3, le 3ème
élément de la liste triée. On remonte ensuite pour trouver successivement les
éléments 4, 5, 6. On explore ensuite le demi-arbre droit qui se développe à
partir de 6. On va jusqu'à l'élément le plus à gauche, à savoir 7. C'est
l'élément suivant de notre liste triée. On explore maintenant le demi-arbre
droit qui se développe à partir de cet élément et on se déplace jusqu'à sa
feuille la plus à gauche. On y trouve 8. C'est l'élément suivant de notre
liste triée. On remonte ensuite pour trouver 9, le dernier élément.
entité EntierPtr
composantes: Data: entier
Gauche, Droite: pointeur
fent
fichier de entier: FIn
entier: N
pointeur: Root, q
procédure Add(¯Root, ¯q)
paramètre: Root, q: pointeur
pointeur: Curr
booléen: Done
Curr ß Root
Done ß FALSE
tant que NOT Done faire
si Data de [q]<Data de [Curr] alors si Gauche de [Curr]=L alors Gauche de [Curr] ß q
Done ß TRUE
sinon Curr ß Gauche de [Curr]
fsi
sinon si Droite de [Curr]=L alors Droite de [Curr] ß q
sinon Curr ß Droite de [Curr]
Done ß TRUE
fsi
fsi
ftant
fproc
procédure Explore(p)
paramètre: p: pointeur
si p=L alors
sinon Explore(Gauche de [p])
écrire Data de [p]
Explore(Droite de [p])
fsi
fproc
FIn ß "entier.dat"
ouvrir FIn
lire N sur FIn
Root ß L
tant que NOT EOF(FIn) faire
q ß nouveau EntierPtr
Data de [q] ß N
Gauche de [q] ß L
Droite de [q] ß L
si Root=L alors Tete ß q
sinon Add(Root, q)
fsi
lire N sur FIn
ftant
fermer FIn
Explore(Root)