Obligement - L'Amiga au maximum

Vendredi 29 mars 2024 - 09:43  

Translate

En De Nl Nl
Es Pt It Nl


Rubriques

Actualité (récente)
Actualité (archive)
Comparatifs
Dossiers
Entrevues
Matériel (tests)
Matériel (bidouilles)
Points de vue
En pratique
Programmation
Reportages
Quizz
Tests de jeux
Tests de logiciels
Tests de compilations
Trucs et astuces
Articles divers

Articles in english


Réseaux sociaux

Suivez-nous sur X




Liste des jeux Amiga

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


Trucs et astuces

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


Glossaire

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


Galeries

Menu des galeries

BD d'Amiga Spécial
Caricatures Dudai
Caricatures Jet d'ail
Diagrammes de Jay Miner
Images insolites
Fin de jeux (de A à E)
Fin de Jeux (de F à O)
Fin de jeux (de P à Z)
Galerie de Mike Dafunk
Logos d'Obligement
Pubs pour matériels
Systèmes d'exploitation
Trombinoscope Alchimie 7
Vidéos


Téléchargement

Documents
Jeux
Logiciels
Magazines
Divers


Liens

Associations
Jeux
Logiciels
Matériel
Magazines et médias
Pages personnelles
Réparateurs
Revendeurs
Scène démo
Sites de téléchargement
Divers


Partenaires

Annuaire Amiga

Amedia Computer

Relec


A Propos

A propos d'Obligement

A Propos


Contact

David Brunet

Courriel

 


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" :

Algorithmes

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.

Algorithmes
Algorithmes

Le parcours postfixé

Il consiste à scruter successivement le fils gauche, le fils droit, puis le père.

Algorithmes

Le parcours préfixé

Il consiste à scruter successivement le père, le fils gauche, puis le fils droit.

Algorithmes

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

A*(((B+C)*(D*E))+F)


[Retour en haut] / [Retour aux articles] [Article précédent] / [Article suivant]