Représentation d'un arbre à l'aide d'un tableau

xjingyu · Message par **xjingyu** » 30 juin 2008 18:30

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?

raorg · Message par **raorg** » 30 juin 2008 20:01

Ben, dans t tu mets le père de i?

xjingyu · Message par **xjingyu** » 30 juin 2008 21:15

Ah oui! Pas bête du tout ^^.
Je vais essayer de le faire ainsi.
Par contre, pour le parcours de l'arbre, ce sera peut-être un petit peu plus compliqué.
Merci Raorg.

Alban · Message par **Alban** » 01 juil. 2008 00:45

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 ?

xjingyu · Message par **xjingyu** » 01 juil. 2008 10:44

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.