Arbres n-aires

L'objectif est de construire un arbre n-aire et de l'afficher graphiquement. Le programme doit prendre en entrée une série de lignes de la forme <père,fils> : 

titi	toto
titi	tata
toto	x
titi	bill
Chaque mot (sans espace) est un nom de noeud. Les noms sont uniques (le fichier est correct, vous n'avez aucune vérification à faire). Le premier mot de la première ligne est la racine. Pour toutes les autres lignes, un mot apparaissant en colonne gauche aura toujours été cité préalablement en colonne droite (autrement dit, l'arbre est construit à partir de la racine). Quand un noeud est rajouté, il doit apparaître à droite des fils déjà insérés.

A titre d'exemple l'arbre correspondant est le suivant:

Vous devez ensuite afficher l'arbre graphiquement (affichage graphique).

Structure de données

On suggère (ce n'est qu'une suggestion) pour la représentation de l'arbre la structure de donnée suivante: 
type
	string = packed array[1..50] of char;

	arbre = ^cellule;
	cellule = record
			nom          : string;
			premier_fils : arbre;
			frere        : arbre
			x            : integer; { La position du noeud a l'écran }
			width        : integer
		end;

Algorithme

Pour "placer" un arbre, c'est à dire calculer la position de tous les noeud, on suggère l'algorithme suivant (là encore, ce n'est qu'une suggestion):
  1. On fait une première passe pour calculer la largeur du sous arbre sous chaque noeud. La largeur est la suivante: pour une feuille (pas de fils), la largeur est celle du noeud; pour tous les autres (noeuds internes), la largeur est la somme de la largeur des fils.
  2. On calcule la position de chaque noeud, en le plaçant par exemple au milieu d'une bande suffisament large pour contenir le noeud et ses fils.
Christophe Tronche, ch@tronche.com