Les Arbres Binaires

[Dhalluine]

Bonjour,
J'ai un exercice dans lequel je dois réaliser une procédure imprimer qui imprimer l'arbre a sous forme préfixé.
Voici l'énoncé exact :

imprimer imp a : imprime l'arbre a sous forme préfixée complètement parenthésée en utilisant l'imprimeur imp pour imprimer les étiquettes des noeuds de l'arbre.
L'arbre vide est imprimé par le couple de parenthèses ().
de type 'a -> unit) -> 'a t -> unit

seulement, je ne sais pas de quel type sont les étiquettes de l'arbre.


J'ai pensé à diverses méthodes mais qui n'ont jamais aboutis.

Je vous demande alors de l'aide (juste me mettre sur la piste svp) .
Merci

[Cacophrene]

Bonsoir,

je ne sais pas de quel type sont les étiquettes de l'arbre.

On te demande de créer une fonction imp dont on te donne la signature :

val imp : ('a -> unit) -> 'a t -> unit

Tu peux en déduire que ta fonction va recevoir deux paramètres en entrée : une fonction de type 'a -> unit qui affiche une valeur de type quelconque 'a (ce type désigne donc les étiquettes de ton arbre binaire) et un arbre binaire, de type 'a t.

Je te donne la piste suivante :

type 'a t = Leaf | Node of 'a t * 'a * 'a t

À toi de voir ce que tu peux en faire pour écrire la fonction imp !

Cordialement,
Cacophrène

[Dhalluine]

Ce que je ne comprends pas c'est quelle est l'argument que doit prendre imp?

vu que la fonction imprimer doit être de la forme : imprimer imp a , logiquement imp prend a en argument, mais dans ce cas là imp serait de type :
'a t -> unit, non?
alors que imp doit être de type 'a -> unit.



J'ai vraiment du mal........

[prgasp77]

Il faut comprendre que le but est de diviser en deux le problème. Afficher un arbre est en effet deux problèmes : son parcourt d'une part et l'impression de ses feuilles d'autre part. La fonction imprimer s'occupe de la première partie, et la fonction imp de la seconde : imprimer imp tree parcourt l'arbre tree et pour chacune de ses feuilles leaf appelle imp leaf.

Donc,

• imp a pour signature 'a -> unit (imprime une feuille de l'arbre) ;
• imprimer a pour signature ('a -> unit) -> 'a t -> unit (appelle la fonction donnée en argument pour chacune des feuilles de leaf).

Pour résumer, appeler imprimer en fournissant la fonction print_int et l'abre Node ( (Leaf 3), 5 (Node (Leaf 0, 42, Leaf 7)) ) sera équivalent à l'appel successif de :

Code ocaml :

1
2
3
4
5
6
print_int 5 ;
print_int 3 ;
print_int 42 ;
print_int 0 ;
print_int 7

Ça va mieux ?


Edit : oui j'ai pris une représentation étrange pour mon type d'arbre .

[Dhalluine]

En fait, ce que je ne comprends pas c'est :
pour la fonction imp, de dois me servir du Printf, mais de quel type seront les étiquettes? (dois -je mettre printf "%c" ? ou printf "%d"? etc.....)

(c'est probablement bête comme question, mais j'ai vraiment du mal sur cette question précise )

[prgasp77]

On ne te demande pas de coder imp, mais imprimer. C'est l'utilisateur de la fonction imprimer qui fournira la bonne fonction imp en fonction du type de l'arbre qu'il veut utiliser.

Tu dois comprendre que tu fais de la programmation fonctionnelle, les fonctions sont des arguments.

[Cacophrene]

Bonjour,

Un petit coup de pouce supplémentaire avec le squelette de la fonction imprimer. C'est une illustration de ce que te disais prgasp77 à propos de scinder le problème en deux sous-problèmes parcours/affichage. À toi de remplacer les points de suspension par du code. Courage, tu y es presque !

Code :

1
2
3
4
let rec imprimer imp = function
  | Leaf -> ...
  | Node (left, x, right) -> ...

Cordialement,
Cacophrène