Informatique pour les sciences humaines

Deuxième année (BA3a)

Tp8

Date de reddition le 14 février 2006 à 9h

Implémentation des arbres généralisés

Présentation

Un arbre général (ou arbre n-aire) est un arbre dans lequel chaque noeud a un nombre variable de fils. Les enfants d’un nœud doivent être représentés comme élément d’une liste chaînée.

Nous optons pour une représentation binaire dans laquelle chaque nœud admet deux pointeurs : l’un vers son fils le plus à gauche, l’autre vers le frère le plus à droite.

L’utilisation d’une liste doublement chaînée pour stocker les enfants ainsi qu’un pointeur depuis le frère le plus à droit vers le père permet un déplacement facilité dans l’arbre.

Faire une implémentation d’une structure d’arbre généralisé (arbre n-aire) qui suit le modèle ci-dessus.

Faire une procédure pour ajouter un nœud-enfant dans la liste des nœud-enfants d’un nœud-père

Ecrire une fonction de parcours de l’arbre