Discussion :

[sorcierombre]

Bonjour,
J'ai un arbre n-aire dont j'ai défini le type

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
type arbre =
	  fin
	  |Pere of valeur*arbre list 
	  |Feuille of valeur;;

Et j'ai besoin de trouver la plus longue branche ;
l'arbre me sert a représenter des combinaison de longueur diverse d’où l'utilisation d'un constructeur fin qui m'indique qu'une des combinaison s’arrête la;
Mon problème est que je n'ai pas le droit d'utiliser les références .
avec les références j'aurais indiqué pour chaque feuille a quelle étage elle se trouve , puis prenant la feuille la plus basse , je serais remonté,
Sauf que mon type d'arbre ne me le permet pas.
J'ai une fonction qui me permet d'afficher toutes les combinaisons de mon arbre sous forme de liste. Mais l'utilisation de l'arbre me permet de gagner du temps de calcul , et trouver la plus longue combinaison a partir des listes des combinaisons retire tout l’intérêt a l'usage d'un arbre.
Quelqu'un aurait une piste pour moi (même formulé en français, j'essaierai de trouver la fonction associée

[drunkskater]

Salut,

Désolé mais je te réponds à toute vitesse avant d'aller en cours, j'espère ne pas être passé à coté de ta questions. Fais-moi signe si c'est le cas !

Sans trop réfléchir : ce que tu peux faire facilement c'est parcourir ton arbre en stockant au fur et à mesure la plus grande profondeur trouvée (pour ça il faut que tu aies deux arguments dans ta fonction : un qui correspond à la plus grande profondeur trouvée à ce stade et un correspondant à la profondeur actuelle; une fois le parcours terminé tu renvoies la plus grande valeur trouvée)

Ceci dit si tu dois parcourir ton arbre à chaque fois que tu veux sa hauteur, ce n'est pas optimal. Du coup le plus simple serait peut-être de stocker la hauteur et de la mettre à jour au fur et à mesure de la construction de l'arbre.

J'espère pas avoir dit de conneries. J'ai cours à 13h30 donc je peux pas t'aider beaucoup plus pour l'instant, mais si tu m'en dis plus sur ce que tu veux faire je veux bien essayer de t'aider (essayer hein )

[sorcierombre]

Je ne souhaite pas la hauteur de la plus longue branche , mais toute la branche entière .
Donc il me faut garder tout le chemin permettant d'acceder a cette branche la plus profonde.

[SpiceGuid]

Le chemin est simplement une liste d'entiers où [] désigne le nœud racine et où, dans h::t :

• h désigne un indice dans la liste des arbres enfants
• t désigne le chemin déjà parcouru depuis la racine

[sorcierombre]

Eureka ce matin en me levant j'ai trouvé la solution qui me convenait.
Mon souci principal ,etait que lorsque je me trouvais face a un noeud (comme dans un labyrinthe) je ne savais pas vers quelle branche me tourner car rien de ne presagais de sa longueur.
Il m'as suffit d'utiliser une fonction qui me donne la longueur d'une branche.
A partir de ca j'ai créé une fonction qui compare deux branches et me retourne la plus longue.
On fait un fold left pour comparer les branches deux a deux et ne garder que la plus longue. on note le contenu de la valeur du noeud et on reapplique la meme fonction a ses enfants .
A tous les etudiants de l'n7 bon courage , le rendu est vendredi. Je poste ma solution ici au cas ou certains soient encore bloqué la.