IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Caml Discussion :

Les Arbres Binaires


Sujet :

Caml

  1. #1
    Candidat au Club
    Femme Profil pro
    Etudiante
    Inscrit en
    Septembre 2012
    Messages
    5
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France

    Informations professionnelles :
    Activité : Etudiante

    Informations forums :
    Inscription : Septembre 2012
    Messages : 5
    Points : 3
    Points
    3
    Par défaut Les Arbres Binaires
    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

  2. #2
    Membre éprouvé
    Avatar de Cacophrene
    Homme Profil pro
    Biologiste
    Inscrit en
    Janvier 2009
    Messages
    535
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Royaume-Uni

    Informations professionnelles :
    Activité : Biologiste

    Informations forums :
    Inscription : Janvier 2009
    Messages : 535
    Points : 1 125
    Points
    1 125
    Par défaut
    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

  3. #3
    Candidat au Club
    Femme Profil pro
    Etudiante
    Inscrit en
    Septembre 2012
    Messages
    5
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France

    Informations professionnelles :
    Activité : Etudiante

    Informations forums :
    Inscription : Septembre 2012
    Messages : 5
    Points : 3
    Points
    3
    Par défaut
    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........

  4. #4
    Membre émérite
    Avatar de prgasp77
    Homme Profil pro
    Ingénieur en systèmes embarqués
    Inscrit en
    Juin 2004
    Messages
    1 306
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : France, Eure (Haute Normandie)

    Informations professionnelles :
    Activité : Ingénieur en systèmes embarqués
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : Juin 2004
    Messages : 1 306
    Points : 2 466
    Points
    2 466
    Par défaut
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 .
    -- Yankel Scialom

  5. #5
    Candidat au Club
    Femme Profil pro
    Etudiante
    Inscrit en
    Septembre 2012
    Messages
    5
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France

    Informations professionnelles :
    Activité : Etudiante

    Informations forums :
    Inscription : Septembre 2012
    Messages : 5
    Points : 3
    Points
    3
    Par défaut
    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 )

  6. #6
    Membre émérite
    Avatar de prgasp77
    Homme Profil pro
    Ingénieur en systèmes embarqués
    Inscrit en
    Juin 2004
    Messages
    1 306
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : France, Eure (Haute Normandie)

    Informations professionnelles :
    Activité : Ingénieur en systèmes embarqués
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : Juin 2004
    Messages : 1 306
    Points : 2 466
    Points
    2 466
    Par défaut
    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.
    -- Yankel Scialom

  7. #7
    Membre éprouvé
    Avatar de Cacophrene
    Homme Profil pro
    Biologiste
    Inscrit en
    Janvier 2009
    Messages
    535
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Royaume-Uni

    Informations professionnelles :
    Activité : Biologiste

    Informations forums :
    Inscription : Janvier 2009
    Messages : 535
    Points : 1 125
    Points
    1 125
    Par défaut
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    let rec imprimer imp = function
      | Leaf -> ...
      | Node (left, x, right) -> ...
    Cordialement,
    Cacophrène

Discussions similaires

  1. Cours sur les arbres binaires
    Par Fredo123456 dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 09/10/2008, 17h45
  2. Questions diverses sur les Arbres binaires + insertion d'un fils
    Par beegees dans le forum Algorithmes et structures de données
    Réponses: 5
    Dernier message: 18/03/2008, 02h21
  3. Demande sur les arbres binaire
    Par IDE dans le forum C++
    Réponses: 12
    Dernier message: 02/12/2007, 18h55
  4. Les arbres binaire en java
    Par vincem35 dans le forum Langage
    Réponses: 3
    Dernier message: 15/11/2007, 20h44
  5. Java et les arbres binaires
    Par Noutch dans le forum JBuilder
    Réponses: 1
    Dernier message: 17/08/2007, 15h25

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo