Tri par arbre binaire.


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)



Page précédente.
Page d'accueil.