Suivez-nous sur X
|
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z,
ALL
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
A propos d'Obligement
|
|
David Brunet
|
|
|
|
En pratique : Algorithmes et structures de données - Les arbres
(Article écrit par Lucien Turski-Marcon et Bruno Bailluet et extrait d'Amiga News Tech - mai 1992)
|
|
Nous nous attaquons aujourd'hui aux arbres, structure de données utilisée dans des domaines très divers, tels que
les bases de données hiérarchiques, ou encore la compression (méthode Huffman).
Si vous n'êtes pas très familiers avec les arbres, c'est le moment ou jamais. Pour ne pas échapper au rite, une
petite définition : un arbre binaire est une structure hiérarchique dans laquelle chaque niveau se compose d'un
ou plusieurs noeuds, chaque noeud n'ayant que deux fils au maximum. Mais abandonnons-nous plutôt au célèbre proverbe populaire :
"un petit dessin vaut mieux qu'un long discours" :
Comme nous pouvons le constater, il existe différents types de noeuds, suivant leur position dans l'arbre.
- La racine ("root" en anglais) est le noeud représentant le sommet de l'arbre. Ce noeud n'a pas de père,
ce qui signifie qu'il n'est pointé par aucun autre noeud.
- Les feuilles ("leaves" en anglais) sont les noeuds terminaux de l'arbre. Ils n'ont pas de fils mais
ont un seul père.
- Les noeuds intermédiaires n'appartiennent pas aux deux catégories précédemment citées, ce sont
simplement des noeuds de liaison. Ils ont un seul père et un ou deux fils. On pourrait les appeler les
branches, si l'on se laissait aller à un humour bassement arboricole...
L'arbre, comme toutes les autres structures, dispose de méthodes particulières permettant de le
parcourir afin d'y retrouver les données insérées.
Il existe différents types de parcours pour notre arbre, sachant que chacun d'eux conditionne l'ordre
de sortie des données.
Le parcours infixé
Il consiste à scruter successivement le fils gauche, le père, puis le fils droit.
Le parcours postfixé
Il consiste à scruter successivement le fils gauche, le fils droit, puis le père.
Le parcours préfixé
Il consiste à scruter successivement le père, le fils gauche, puis le fils droit.
Sans plus tarder, voici le programme du mois : il construit un arbre à partir d'une expression
de votre choix, celle-ci se trouvant dans un fichier dont le nom doit être passé en paramètre.
Un exemple d'une telle expression est donné en second listing.
Vous pourrez aussi constater que les deux méthodes de parcours choisies (postfixé et infixé) donnent
des résultats différents : le parcours infixé ressort l'expression entrée telle quelle, alors que
le parcours postfixé la ressort en notation polonaise inversée. Ajoutons que la création de l'arbre
se fait à l'aide d'une pile.
Sur ce, rendez-vous au mois prochain pour le début des algorithmes de tri.
Listing 1 : Arbre.c
/* Compile avec LC -Lm -O */
#include <exec/types.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define issigne(c) (c == '+' || c == '*' || c == '/' || c == '-')
#define FEUILLE(x) ((x -> gauche == NULL) && (x -> droite == NULL))
struct Arbre {
char nom ;
struct Arbre *gauche ;
struct Arbre *droite ;
} ;
struct Pile_ptr {
struct Arbre *info ;
struct Pile_ptr *suivant ;
} ;
struct Pile_ptr *base ;
VOID Empile (struct Arbre *) ;
struct Arbre *Depile (VOID) ;
BOOL Pile_Vide (VOID) ;
VOID Construit (VOID) ;
VOID Explore_Postfixe (struct Arbre *) ;
VOID Explore_Infixe (struct Arbre *) ;
main(int argc, char **argv)
{
char c ;
struct Arbre *temp, *debut ;
FILE *fichier ;
base = (struct Pile_ptr *) malloc (sizeof (struct Pile_ptr)) ;
base -> info = NULL ;
base -> suivant = NULL ;
fichier = fopen (argv[1],"r") ;
if (! fichier)
{
puts ("Fichier introuvable !!!") ;
exit (5) ;
}
while ( fscanf (fichier,"%c",&c) != EOF)
{
switch (c)
{
case ')':
Construit() ;
break ;
default:
if ( (issigne (c)) || (isalpha (c)) )
{
temp = (struct Arbre *) malloc (sizeof (struct Arbre)) ;
temp -> nom = c ;
temp -> gauche = NULL ;
temp -> droite = NULL ;
Empile (temp) ;
}
break ;
}
}
Construit() ;
debut = Depile() ;
printf ("Exploration postfixee (gauche,droit,racine) : ") ;
Explore_Postfixe (debut) ;
printf ("\nExploration infixee (gauche,racine,droit) : ") ;
Explore_Infixe (debut) ;
printf ("\n") ;
free (base) ;
}
VOID Empile (struct Arbre *tree)
{
struct Pile_ptr *nouveau ;
nouveau = (struct Pile_ptr *) malloc (sizeof (struct Pile_ptr)) ;
nouveau -> suivant = base -> suivant ;
base -> suivant = nouveau ;
nouveau -> info = tree ;
}
struct Arbre *Depile (VOID)
{
struct Pile_ptr *element ;
struct Arbre *val ;
element = base -> suivant ;
base -> suivant = element -> suivant ;
val = element -> info ;
free (element) ;
return (val) ;
}
BOOL Pile_Vide (VOID)
{
if (! base -> suivant)
return (TRUE) ;
else
return (FALSE) ;
}
VOID Construit (VOID)
{
struct Arbre *tree ;
struct Arbre *fils_droit ;
struct Arbre *fils_gauche ;
fils_droit = Depile() ;
tree = Depile() ;
fils_gauche = Depile() ;
tree -> gauche = fils_gauche ;
tree -> droite = fils_droit ;
Empile (tree) ;
}
VOID Explore_Postfixe (struct Arbre *tree)
{
struct Arbre *courant ;
courant = tree ;
if (courant -> gauche)
Explore_Postfixe (courant -> gauche) ;
if (courant -> droite)
Explore_Postfixe (courant -> droite) ;
printf ("%c",courant -> nom) ;
}
VOID Explore_Infixe (struct Arbre *tree)
{
struct Arbre *courant ;
courant = tree ;
if (courant -> gauche)
{
printf ("(") ;
Explore_Infixe (courant -> gauche) ;
}
printf ("%c",courant -> nom) ;
if (courant -> droite)
Explore_Infixe (courant -> droite) ;
if (! FEUILLE (courant))
printf (")") ;
}
|
Listing 2 : Exemple de fichier expression
|