Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 12 sur 12
  1. #1
    Nouveau Membre du Club
    Profil pro
    Étudiant
    Inscrit en
    mars 2005
    Messages
    24
    Détails du profil
    Informations personnelles :
    Âge : 28
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mars 2005
    Messages : 24
    Points : 29
    Points
    29

    Par défaut Arbres binaires

    je pense qu'une partie consacrée aux arbres serait la bienvenue !!
    - comment créer un arbre binaire ?
    - quelles sont les fonctions de bases pour manipuler des arbres binaires ?

    j'ai moi même besoin d'aide concernant les arbres en C notamment à cause des pointeurs et j'ai du mal à m'en sortir !

    réponses aux 2 questions :

    + Un abre binaire est une suite de pointeurs, chaque pointeurs pointe une structure dans laquelle on peut mettre une valeur (int ou char par exemple) ainsi que 2 champs pointant les structures suivantes (appelées fils gauche et fils droit). En clair : un arbre généalogique est un arbre binaire à l'envers.

    Code :
    1
    2
    3
    4
    5
    6
    7
    struct elem{
    	char lettre;
    	struct elem* fg;
    	struct elem* fd;
    } t_noeud;
    typedef struct elem noeud;
    typedef struct elem *arbre;
    + Voila les fonctions de base :

    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    boolean estvide(arbre a)
    	{return a==NULL;}
     
    /*** A noter qu'en C le type booleen n'est pas defini il faut donc le definir auparavent comme ceci par exemple : 
    #define FALSE 0
    #define TRUE  1
    typedef unsigned char boolean; 
    ***/
     
    arbre gauche(arbre a)
    	{return a->fg;}
     
    arbre droit(arbre a)
    	{return a->fd;}
     
    char valeur(arbre a)
    	{return a->lettre;}
     
    arbre cons(char c, arbre filsg, arbre filsd)
    	{
    	arbre p;
    	p=(arbre)malloc(sizeof(noeud));
    	p->lettre=c;
    	p->fg=filsg;
    	p->fd=filsd;
    	return p;
    	}
     
    /*** Cette fonction sert a construire un arbre exemple : cons(T,cons(A,NULL,NULL),cons(W,NULL,NULL));
    ici T pointe vers A vers la gauche et W vers à droite, A et W pointant vers NULL pour signaler la fin de l'arbre.
    ***/

  2. #2
    Modérateur
    Avatar de PRomu@ld
    Homme Profil pro Romuald Perrot
    Ingénieur de Recherche
    Inscrit en
    avril 2005
    Messages
    4 160
    Détails du profil
    Informations personnelles :
    Nom : Homme Romuald Perrot
    Âge : 29
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur de Recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : avril 2005
    Messages : 4 160
    Points : 5 585
    Points
    5 585

    Par défaut

    Personnellement, je ne pense pas que celà devrait faire partie de la fac, ce n'est pas un problème du langage, tout ceci devrai être dans la partie source.

  3. #3
    gl
    gl est déconnecté
    Rédacteur/Modérateur

    Homme Profil pro
    Inscrit en
    juin 2002
    Messages
    2 096
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 35
    Localisation : France, Isère (Rhône Alpes)

    Informations forums :
    Inscription : juin 2002
    Messages : 2 096
    Points : 3 957
    Points
    3 957

    Par défaut

    Citation Envoyé par PRomu@ld
    Personnellement, je ne pense pas que celà devrait faire partie de la fac, ce n'est pas un problème du langage, tout ceci devrai être dans la partie source.

    Entierement d'accord avec toi. J'ai d'ailleur modifier le TAG de la question

  4. #4
    Rédacteur/Modérateur

    Avatar de millie
    Profil pro
    Inscrit en
    juin 2006
    Messages
    6 945
    Détails du profil
    Informations personnelles :
    Localisation : Luxembourg

    Informations forums :
    Inscription : juin 2006
    Messages : 6 945
    Points : 8 774
    Points
    8 774

    Par défaut

    Citation Envoyé par wincher
    Code :
    1
    2
    boolean estvide(arbre a)
    	{return a==NULL;}

    Je trouve que ce genre de declaration (desole, je suis sur qwerty) est a eviter, sans connaitre l'implementation, on pourrait croire que l'arbre a est mis entierement sur la pile (alors que ce n'est qu'un pointeur).


    p=(arbre)malloc(sizeof(noeud));
    Le cast est inutile.

    Tu n'as definis aucun destructeur... Je trouves qu'il manque des operations tel que : estFeuille.

    Une operation de parcours serait egalement utile, car ici, sans connaitre l'implementation, on serait oblige d'effectuer des appels recursifs (a eviter en C, il peut vite y avoir un debordement de pile).
    Je ne répondrai à aucune question technique en privé

  5. #5
    Expert Confirmé Sénior Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    septembre 2005
    Messages
    24 031
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 30
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : septembre 2005
    Messages : 24 031
    Points : 32 201
    Points
    32 201

    Par défaut

    Pour un arbre à chaînage simple, de toute façon, il faudra forcément une pile (qu'elle soit sur la pile du programe (récursif pur) ou sur le tas("itératif avec pile")) pour faire un parcours...
    SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.

    "Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
    Apparently everyone.
    -- Raymond Chen.
    Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.

  6. #6
    Membre du Club
    Profil pro
    Inscrit en
    octobre 2005
    Messages
    90
    Détails du profil
    Informations personnelles :
    Âge : 27
    Localisation : Algérie

    Informations forums :
    Inscription : octobre 2005
    Messages : 90
    Points : 50
    Points
    50

    Par défaut

    Citation Envoyé par Médinoc
    Pour un arbre à chaînage simple, de toute façon, il faudra forcément une pile (qu'elle soit sur la pile du programe (récursif pur) ou sur le tas("itératif avec pile")) pour faire un parcours...
    Pour quel type de parcours?
    Ca ne me semble pas impossible de parcourir un arbre sans utilisé de pile, mais juste avec 1 ou 2 variable temporaires.

  7. #7
    Expert Confirmé Sénior Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    septembre 2005
    Messages
    24 031
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 30
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : septembre 2005
    Messages : 24 031
    Points : 32 201
    Points
    32 201

    Par défaut

    Pour un parcours en profondeur : Avec un chaînage simple, une pile est indispensable pour remonter.
    SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.

    "Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
    Apparently everyone.
    -- Raymond Chen.
    Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.

  8. #8
    Membre du Club
    Profil pro
    Inscrit en
    octobre 2005
    Messages
    90
    Détails du profil
    Informations personnelles :
    Âge : 27
    Localisation : Algérie

    Informations forums :
    Inscription : octobre 2005
    Messages : 90
    Points : 50
    Points
    50

    Par défaut

    Citation Envoyé par Médinoc
    Pour un parcours en profondeur : Avec un chaînage simple, une pile est indispensable pour remonter.
    nono, si tu parle juste de parcourir un arbre bianaire, j'essayerai de donner un pseudo code si t'es pas convaincu.

  9. #9
    Expert Confirmé Sénior Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    septembre 2005
    Messages
    24 031
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 30
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : septembre 2005
    Messages : 24 031
    Points : 32 201
    Points
    32 201

    Par défaut

    Donne donc.
    SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.

    "Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
    Apparently everyone.
    -- Raymond Chen.
    Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.

  10. #10
    Membre du Club
    Profil pro
    Inscrit en
    octobre 2005
    Messages
    90
    Détails du profil
    Informations personnelles :
    Âge : 27
    Localisation : Algérie

    Informations forums :
    Inscription : octobre 2005
    Messages : 90
    Points : 50
    Points
    50

    Par défaut

    Citation Envoyé par Médinoc
    Pour un parcours en profondeur : Avec un chainage simple, une pile est indispensable pour remonter.
    Je viens de comprendre notre différant, je suppose que dans ton arbre, tu n'as pas de champs père ? Si c'est le cas je m'excuse de pas avoir prévenu plus tôt et effectivement la pile et obligatoire.

  11. #11
    Expert Confirmé Sénior Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    septembre 2005
    Messages
    24 031
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 30
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : septembre 2005
    Messages : 24 031
    Points : 32 201
    Points
    32 201

    Par défaut

    En effet, c'est ce que je voulais dire par "avec un chaînage simple".
    SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.

    "Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
    Apparently everyone.
    -- Raymond Chen.
    Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.

  12. #12
    Rédacteur
    Avatar de Franck.H
    Homme Profil pro Franck HECHT
    Développeur .NET
    Inscrit en
    janvier 2004
    Messages
    6 616
    Détails du profil
    Informations personnelles :
    Nom : Homme Franck HECHT
    Âge : 37
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Développeur .NET
    Secteur : Service public

    Informations forums :
    Inscription : janvier 2004
    Messages : 6 616
    Points : 11 308
    Points
    11 308

    Par défaut

    Ouch Il est vieux ce post dis donc Ca me semble un peu légé pour ajouter ca dans les sources, pas de structuration de la source etc...C'est un peu donné à la va-vite.

    Le code lui même n'est pas au top, aucun test sur les arguments ni même sur les allocations de mémoire etc... vraiment aucun sécurité

    Dommage
    Mon Site
    Nouvelle version 3.1.0 de ma bibliothèque de gestion des chaînes de caractères en C

    L'imagination est plus importante que le savoir. A. Einstein

    Je ne répond à aucune question technique par MP, merci d'avance !

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •