Bonjour,
j'aurai une petite question à propos de la représentation d'un arbre sous Caml.
En regardant les sujets de TP d'algo des ENS, je suis tombé sur un sujet utilisant des arbres. (Concours 2006 : Arbres Philogénétiques)
Il est écrit dans le rapport qu'on pouvait représenter ces arbres sous forme de tableau.
Mais je n'ai pas réussit à construire de manière efficace un tel tableau.
Dans le cas des arbres binaires, on pourrait indiquer que les fils d'un nœud "i" sont dans les cases "2.i" et "2.i+1".
Mais dans le cas général, où chaque nœud peut avoir un nombre différent de fils, je ne vois pas trop comment représenter un tel arbre.
Y a-t-il une manière efficace pour construire un tel tableau?
Représentation d'un arbre à l'aide d'un tableau
Je ne suis pas trop familier de ce genre de choses, mais ça te parle ça : http://www.dailly.info/algorithmes-de-tri/abr.php ?
Dans le lien que tu m'as proposé, ils traitent du cas des arbres binaires, et la représentation par une liste n'est pas vraiment ce que je cherche.
Mais merci quand même.
Sinon je viens de penser à une nouvelle représentation possible.
On peut construire une matrice NxN (N=nombre de noeuds plus feuilles), et dans la case T.(i).(j) on met "1" si j est fils de i, "0" s'il n'y a pas de lien entre eux et si l'on souhaite "-1" si j est le père de i.
Bon le coût de parcours devient N² mais bon...
Peut-être que ça pourrait intéresser quelqu'un.
Mais merci quand même.
Sinon je viens de penser à une nouvelle représentation possible.
On peut construire une matrice NxN (N=nombre de noeuds plus feuilles), et dans la case T.(i).(j) on met "1" si j est fils de i, "0" s'il n'y a pas de lien entre eux et si l'on souhaite "-1" si j est le père de i.
Bon le coût de parcours devient N² mais bon...
Peut-être que ça pourrait intéresser quelqu'un.