Discussion :

[Keldan]

Salut,

Defini ce type de donée:

Code :

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

type 'a arbre = Node of 'a * 'a arbre list;;

J´ai besoin de trouver la fonction qui calcule la valeur maximum de l´arbre

Code :

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

(‘a arbre -> 'a)

Vous pouvez m´aider?

Merci

[LLB]

Oui.

Où rencontres-tu un problème ? Commence par calculer le maximum d'une liste (List.fold_left peut t'aider). Ensuite, adapte le code pour faire ça récursivement.

[Keldan]

Merci pour l'aide
C'est fait


Qui, j´ai utilissé List.fold_left et List.map

Et pour faire le parcours en preordre d'un arbre ?

J´ai fait ça:

Code :

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

1
2
3
4
let rec p_ord = function
 
     (Node(r,[]))-> [r]
     |(Node(r,l)) -> [r] @ p_ord  l;;

mais pourtant ça donée cette erreur :

Code :

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

This expression has type 'a arbre list but is here used with type 'a arbre

[Steki-kun]

Que dire, tout est dans le message d'erreur non ? Tu appliques p_ord à une liste d'arbres alors que c'est une fonction qui parcourt un arbre et non une liste d'arbres.

[Keldan]

Qui, mais si la logique de la fonction est bonne ...

¿comment je pourrais faire pour l ´applique a une liste d´arbres ?


Merci

[Steki-kun]

Disons que si c'est pas typable la "logique de la fonction" ne peut pas être bonne Plus précisément, tu cherches à traverser un arbre, mais la logique de ta fonction c'est de dire qu'on visite un noeud avant ses sous-arbres (c'est en effet nécessaire pour le préordre), sans pour autant spécifier dans quel ordre on doit visiter ces sous-arbres ! Suivant comment tu traverseras la liste, tu n'obtiendras pas le même parcours... il te faudra donc bien décider comment traverser la liste de sous-arbres d'un noeud donné et l'implémenter.
Soit tu ajoutes une fonction qui sera mutuellement récursive avec p_ord et qui l'appelera sur tous les éléments de la liste dans un "certain" ordre, soit plus probablement tu veux les parcourir dans l'ordre "naturel" de la liste, et dans ce cas un coup de fold_left ou de map + flatten suffisent