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

Contribuez Discussion :

Arbres binaires [Sources]


Sujet :

Contribuez

  1. #1
    Nouveau membre du Club
    Profil pro
    Étudiant
    Inscrit en
    Mars 2005
    Messages
    24
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2005
    Messages : 24
    Points : 35
    Points
    35
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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
    Expert éminent
    Avatar de PRomu@ld
    Homme Profil pro
    Ingénieur de Recherche
    Inscrit en
    Avril 2005
    Messages
    4 155
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France, Vienne (Poitou Charente)

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

    Informations forums :
    Inscription : Avril 2005
    Messages : 4 155
    Points : 6 486
    Points
    6 486
    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

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

    Informations forums :
    Inscription : Juin 2002
    Messages : 2 165
    Points : 4 637
    Points
    4 637
    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

    Avatar de millie
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    7 015
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 7 015
    Points : 9 818
    Points
    9 818
    Par défaut
    Citation Envoyé par wincher
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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 éminent sénior
    Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Septembre 2005
    Messages
    27 369
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : France

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

    Informations forums :
    Inscription : Septembre 2005
    Messages : 27 369
    Points : 41 518
    Points
    41 518
    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 : 36
    Localisation : Algérie

    Informations forums :
    Inscription : Octobre 2005
    Messages : 90
    Points : 66
    Points
    66
    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 éminent sénior
    Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Septembre 2005
    Messages
    27 369
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : France

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

    Informations forums :
    Inscription : Septembre 2005
    Messages : 27 369
    Points : 41 518
    Points
    41 518
    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 : 36
    Localisation : Algérie

    Informations forums :
    Inscription : Octobre 2005
    Messages : 90
    Points : 66
    Points
    66
    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 éminent sénior
    Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Septembre 2005
    Messages
    27 369
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : France

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

    Informations forums :
    Inscription : Septembre 2005
    Messages : 27 369
    Points : 41 518
    Points
    41 518
    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 : 36
    Localisation : Algérie

    Informations forums :
    Inscription : Octobre 2005
    Messages : 90
    Points : 66
    Points
    66
    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 éminent sénior
    Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Septembre 2005
    Messages
    27 369
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : France

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

    Informations forums :
    Inscription : Septembre 2005
    Messages : 27 369
    Points : 41 518
    Points
    41 518
    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
    Développeur .NET
    Inscrit en
    Janvier 2004
    Messages
    6 951
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : France, Haut Rhin (Alsace)

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

    Informations forums :
    Inscription : Janvier 2004
    Messages : 6 951
    Points : 12 462
    Points
    12 462
    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
    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 !

Discussions similaires

  1. Afficher un arbre binaire avec sa structure
    Par PhoneKilleR dans le forum C
    Réponses: 7
    Dernier message: 24/04/2008, 00h24
  2. suppression d'un arbre binaire
    Par NomUtilisateurDejaPris dans le forum C
    Réponses: 11
    Dernier message: 16/02/2004, 11h05
  3. [Arbre binaire de Recherche]
    Par Giovanny Temgoua dans le forum Algorithmes et structures de données
    Réponses: 11
    Dernier message: 06/02/2004, 12h45
  4. Arbre binaire
    Par Heaven dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 02/02/2004, 20h01
  5. [LG]probleme de creation arbre binaire
    Par jsaviola dans le forum Langage
    Réponses: 2
    Dernier message: 06/01/2004, 21h57

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