Breaking News

Cours d’algorithmes

définit la notion d’arbres (informations arborescentes). La plupart des algorithmes utilisent la récursivité qui s’impose pleinement pour le traitement des arbres. Les algorithmes sont concis, naturels, faciles à concevoir et à comprendre dès lors que le concept de récursivité est maîtrisé. De nombreux exemples concrets sont donnés dans ce but. La fin du chapitre présente les arbres ordonnés (les éléments sont placés dans l’arbre suivant un critère d’ordre) pouvant servir d’index pour retrouver rapidement des informations à partir d’une clé. En cas d’ajouts ou de retraits, on peut être amené à réorganiser la structure d’un arbre (le rééquilibrer) pour que les performances ne se dégradent pas trop.
Cours d’algorithmes cliquez ici



Les algorithmes de parcours d’arbre binaire 
Les fonctions de parcours découlent directement des algorithmes vus sur les exemples précédents. Le simple changement de la place de l’ordre d’écriture conduit à un traitement préfixé, infixé ou postfixé. La fonction toString(), passée en paramètre de prefixe() fournit une chaîne de caractères spécifiques de l’objet traité. Cette chaîne est imprimée lors du printf. La fonction toString() est dépendante de l’application et passée en paramètre lors de la création de l’arbre. Par défaut, les objets référencés dans chaque nœud sont des chaînes de caractères.

Algorithmique 
Pour représenter un « grand entier », la démarche la plus naturelle (mais pas la plus économique en place mémoire !) consiste à conserver le nombre sous forme décimale, à chaque chiffre étant associé un caractère. Pour ce faire, on peut choisir de « coder » un tel chiffre par le caractère correspondant (‘0’ pour 0, ‘1’ pour 1…) ; on peut aussi choisir de placer une valeur égale au chiffre lui-même (0 pour 0, 1 pour 1…). La dernière solution oblige à effecteur un « transcodage » lorsque l’on doit passer de la forme chaîne de caractères à la forme big_int (dans le constructeur correspondant, notamment) ou, inversement, lorsqu’on doit passer de la forme big_int à la forme suite de caractères (pour l’affichage). En revanche, elle simplifie quelque peu l’algorithme d’addition, et c’est elle que nous avons choisie.

 Recherche d’un nœud de l’arbre 
La fonction trouverNoeud() recherche récursivement le nœud contenant les informations définies dans objet, dans l’arbre commençant en racine. C’est un parcours d’arbre interrompu (on s’arrête quand on a trouvé un pointeur sur l’objet concerné). Si l’objet n’est pas dans l’arbre, la fonction retourne NULL. Algorithme : la comparaison de deux objets est définie par la fonction comparer() passée en paramètre et spécifique des objets traités dans l’application. Cette fonction est définie lors de la création de l’arbre. Par défaut, il s’agit d’un arbre de chaînes de caractères.