 |
|
|
| |
| TUTORIEL ALGO/METHODES |
|
|
|
| Structure de données : l'arbre |
| Les structures réflexives permettent de traiter l'information de manière plus puissante qu'avec une structure linéaire. Présentation de l'une de ces structures, de son fonctionnement et de ses méthodes de parcours.
(26/07/2005) |
  |
Les structures de données
sont le pain quotidien des développeurs, parfois même sans véritablement
s'en rendre compte. C'est pourquoi trouver la plus adaptée à
un problème relève parfois de la gageure face au nombre de possibilités
et accomplit dans certains cas le plus gros du travail.
Si les tableaux sont aujourd'hui les plus couramment utilisés
chez la plupart des développeurs, l'arbre reste une structure
très puissante de gestion, d'insertion et de recherche de données.
Survol
La comparaison la plus simple reste l'arbre généalogique. Une
racine possède un nombre N de branches, chacune pouvant développer
N branches et ainsi de suite. Cela s'appelle alors un arbre
N-aire. Chaque branche relie deux noeuds entre eux, l'ensemble
permet de définir une hiérarchie. Deux branches ne peuvent pas
mener au même noeud : chaque noeud possède un seul et unique
noeud "père". Un noeud peut disposer de plusieurs branches
ou alors d'aucune (auquel cas ce noeud est appelle "feuille"). Enfin,
la racine est le seul noeud sans père.
Un noeud peut se définir par sa profondeur (nombre de branches
entre le noeud et la racine, plus 1) et sa hauteur (nombre de
branches entre le noeud et la feuille la plus éloignée, plus
1). La racine a donc une profondeur de 1, la hauteur de toute
feuille vaut 1.
Chaque noeud peut être vu comme la racine d'un nouvel arbre
(sauf s'il s'agit d'une feuille), aussi toute méthode de travail
à partir de la racine fonctionnera également à tout niveau inférieur
de la racine.
L'application la plus connue de ce type de structure est le
document XML. Le parcours de ses branches relève de l'analyse
syntaxique. Les algorithmes de cryptographie profitent aussi
de la structure en arbre. Chaque noeud de l'arbre contient une
information, rattachée à celle de son noeud père.
 |
Forum |
|
|
Réagissez
dans les forums
de JDN Développeurs
|
Arbre binaire
Pour mieux se représenter le travail sur un arbre N-aire, il
est courant de partir d'un arbre 2-aire (ou binaire), c'est-à-dire
où chaque noeud possède au plus 2 noeuds fils. De fait, on définit
à partir de chaque noeud disposant de deux noeuds fils un sous-arbre
droit et un sous-arbre gauche, définis à partir de la représentation
graphique de l'arbre.
Parcours d'un arbre
Les données contenues dans l'arbre sont connues en le parcourant,
c'est-à-dire en visitant chaque noeud l'un après l'autre. La
récursivité est pour une bonne part dans l'accomplissement de
ce mécanisme.
Ce parcours de l'arbre permet de construire une séquence du
contenu de chaque noeud, ce qui autorisera son traitement par
d'autres outils (l'arbre en lui-même n'est pas, par défaut,
vu comme une séquence de données).
Il existe plusieurs méthodes de parcours, selon l'ordre dans
lequel celui-ci s'opère. Les trois premiers sont une variation
d'une méthode de parcours dite "en profondeur", où les noeuds
de l'arbre sont atteints branche par branche dans toute leur
profondeur, donc.
La quatrième méthode, "en largeur", parcours les noeuds depuis
la racine, puis niveau par niveau de gauche à droite.
Les méthodes en profondeur scannent récursivement la branche
gauche puis la droite, pour enfin réaliser un traitement spécifique...
Parcours préfixé : le traitement se fait avant
le parcours des sous-arbres.
En pseudo-code :
lire(noeud)
écrire node.valeur
if noeud.gauche != nul alors
lire(noeud.gauche)
if noeud.droite != nul alors
lire(noeud.droite)
Parcours postfixé : le traitement se fait après
le parcours des sous-arbres.
En pseudo-code :
lire(noeud)
if noeud.gauche != nul alors
lire(noeud.gauche)
if noeud.droite != nul alors
lire(noeud.droite)
écrire node.valeur
Parcours infixé : le traitement se fait entre
le parcours de chaque sous-arbre.
En pseudo-code :
lire(noeud)
if noeud.gauche != nul alors
lire(noeud.gauche)
écrire node.valeur
if noeud.droite != nul alors
lire(noeud.droite)
Parcours en largeur : cette
méthode requiert la création d'une liste d'arbres, où sont
notés les noeuds qui ont été lus. Cette méthode n'est pas récursive.
tant que liste.estVide = faux, faire
noeud = liste.retirerQueue
écrire noeud.valeur
si noeud.gauche != nul alors
liste.ajouter(noeud.gauche)
si noeud.droite != nul alors
liste.ajouter(noeud.droite)
fin tant que
Le développeur se retrouve donc avec des séquences pouvant être
très différentes l'une de l'autre, pour un même arbre. Chacune
peut avoir son utilité : le parcours infixé, par exemple, se
montre très utile pour les arbres binaires, car il donne
une séquence croissante. |
|
|
|
|
|
|
|
| Quand achetez-vous le plus en ligne ? |
|
|
|
|
|
|
|
|
| |
|
