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.
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.