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.
Parcours d’un arbre binaire
Un algorithme de parcours d’arbre est un procédé permettant d’accéder à chaque nœud de l’arbre. Un certain traitement est effectué pour chaque nœud (test, écriture, comptage, etc.), mais le parcours est indépendant de cette action et commun à des algorithmes qui peuvent effectuer des traitements très divers comme rechercher les enfants de Gontran, compter la descendance de Julie, compter le nombre de garçons, ajouter un fils à Paul, etc. On distingue deux catégories de parcours d’arbres : les parcours en profondeur et les parcours en largeur. Dans le parcours en profondeur, on explore branche par branche alors que dans le parcours en largeur on explore niveau par niveau.
Algorithme de choix d’un gestionnaire d’exceptions
Lorsqu’une exception est levée par throw, avec le type T, on recherche, dans cet ordre, un gestionnaire correspondant à l’un des types suivants : type T, type de base de T, pointeur sur une classe dérivée (si T est d’un type pointeur sur une classe), type indéterminé (indiqué par catch(...)) dans le gestionnaire.
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.