Arbre binaire

Aller en bas

Arbre binaire

Message  L'alchimiste le Ven 22 Mai - 16:22

Bah c'est simple je sais pas comment ca marche. Alors jai programmé un truc qui me semble bien. Mais est-ce un arbre binaire XD
Si oui cava si non je veux j'aimerais bien qu'on mexplique le fonctionnement ^^

Merci d'avance Smile

Code:
#include "stdio.h"
#include "conio.h"
#include <string.h>
#include "stdlib.h"
//#include <windows.h>



struct Noeud
{
        char mot[25];
        struct Noeud *droite;
        struct Noeud *gauche;
};
struct arbre
{
    struct Noeud *first;
    int taille;
};
//Placer le premier element dans la liste
void add_arbre1(struct arbre *depart,char nom[])
{
    //printf("\nplop");
    depart->first=(struct Noeud*)malloc(sizeof(struct Noeud));
    //printf("\nplop");
    strcpy(depart->first->mot,nom);
    //printf("\n\n %s :",depart->first->mot);
    depart->first->droite=NULL;
    depart->first->gauche=NULL;
}
//Placer lelement à gauche
Noeud* placerG(struct Noeud *a,char nom[])
{
    struct Noeud *gauche;
    gauche=(struct Noeud*)malloc(sizeof(struct Noeud));

    strcpy(gauche->mot,nom);
    gauche->droite=NULL;
    gauche->gauche=NULL;
    a->gauche=gauche;
    //printf("\n %s",cote->mot);
    return a->gauche;
}
//placer l'element à droited l'arbre
Noeud* placerD(struct Noeud *a,char nom[])
{
    struct Noeud *droite;
    droite=(struct Noeud*)malloc(sizeof(struct Noeud));

    strcpy(droite->mot,nom);
    droite->droite=NULL;
    droite->gauche=NULL;
    a->droite=droite;
    //printf("\n %s",cote->mot);
    return a->droite;
}
// Trouver la fin et si ces à gauche ou à droite de la branche
Noeud* add_arbre2(struct Noeud *depart,char nom[])
{
    struct Noeud *a,*d,*g;
    a=depart;
    d=a->droite;
    g=a->gauche;
    int cmp=strcmp(nom,a->mot);
    //printf("\n %d",cmp);

    if(0<cmp)
    {
        return(a->gauche==NULL?placerG(a,nom):add_arbre2(g,nom));
    }
    else if(0>=cmp)
    {
        return(a->droite==NULL?placerD(a,nom):add_arbre2(d,nom));
    }
}
//rechercher un élément
Noeud* recherche(struct Noeud *depart,char nom[])
{
    struct Noeud *a,*d,*g;
    a=depart;
    if(a!=NULL)
    {
        d=a->droite;
        g=a->gauche;
        int cmp=strcmp(nom,a->mot);
        //printf("\n %d",cmp);
        if(0==cmp)
        {
            return(a);
        }
        else if(0<cmp)
        {
            return(a->gauche==NULL?NULL:recherche(g,nom));
        }
        else if(0>cmp)
        {
            return(a->droite==NULL?NULL:recherche(d,nom));
        }
    }
    return(NULL);
}


int main()
{
    struct arbre a,*depart;
    struct Noeud *b;
    depart=&a;
    depart->first=NULL;
    char mot[25];
    char t[3]={'s'};
    //strcpy(t,'-1');
    while(1)
    {
        fflush(stdin);
        printf("\n\n Entrez un mot ou 's' pour sortir: ");
        gets(mot);
        if(!strcmp(mot,t)) break;
        if(depart->first==NULL){add_arbre1(depart,mot);}
        else{b=add_arbre2(depart->first,mot);}
        //printf("\n %s",b->mot);
    }
    printf("\n _______________________________________\n");
    while(1)
    {
        fflush(stdin);
        printf("\n\n Entrez le mot rechercher ou 's' pour sortir: ");
        gets(mot);
        if(!strcmp(mot,t)) break;
        else{b=recherche(depart->first,mot);}
        if(b==NULL){printf("\n Le mot nexiste pas\n");}
        else{printf("\n Nom : %s\n",b->mot);}
    }

    return 1;
}
avatar
L'alchimiste

Messages : 65
Date d'inscription : 06/01/2009
Age : 29

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: Arbre binaire

Message  L'alchimiste le Ven 5 Juin - 16:25

Personne sait ce que cest alors? :'(
avatar
L'alchimiste

Messages : 65
Date d'inscription : 06/01/2009
Age : 29

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: Arbre binaire

Message  Zoners le Sam 6 Juin - 14:51

Je serai aussi interessé de savoir si c'est correct ? si quelqu'un savait repondre ^^ Very Happy
avatar
Zoners

Messages : 84
Date d'inscription : 28/09/2008

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: Arbre binaire

Message  dellC le Sam 6 Juin - 15:12

Le principe est correct, juste que tu as confondu la gauche et la droite ... Ce qui est a gauche est inférieur.
Enfin, c'est peut-être pas indispensable, tant que la fonction de recherche et de création coïncident, ça va. Mais c'est de cette manière qu'on l'a vu au cours


Et aussi, essaye d'améliorer ton code, parce qu'il y est pas super lisible ... Notamment, quand tu mets "0 < cmp", ça peut prêter à confusion, "cmp > 0" est plus logique.
avatar
dellC

Messages : 120
Date d'inscription : 07/11/2008
Age : 29
Localisation : Herve

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: Arbre binaire

Message  Napo le Sam 6 Juin - 17:34

j'ai une petite question sur 2 fonctions --> ORIG( List edge) et DEST(List edge)
Quelqu'un pourrait m'expliquer ce qu'elle font exactement svp?
avatar
Napo

Messages : 27
Date d'inscription : 07/10/2008
Age : 29
Localisation : Jupille

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: Arbre binaire

Message  L'alchimiste le Sam 6 Juin - 17:40

Merci.
oui cmp>0 ou inverse
on nous a pas vraiment appris la logique entre guillemet :s
Enfin je pense Oo.

sinon je venais juste de faire des recherches la-dessus.
Le code que j'ai fait n'est pas un arbre binaire, mais un arbre binaire de recherche!!!
Ce n'es pas la même chose les 2 XD.
On sait passer de l'arbre binaire à l'arbre binaire de recherche en triant(heapSort, si je ne me rompe pas).
Mais ils ne sont pas créés de la même manière!


Arbre binaire :

En informatique, un arbre binaire est une structure de données qui peut se représenter sous la forme d'une hiérarchie dont chaque élément est appelé nœud, le nœud initial étant appelé racine. Dans un arbre binaire, chaque élément possède au plus deux éléments fils au niveau inférieur, habituellement appelés gauche et droit. Du point de vue de ces éléments fils, l'élément dont ils sont issus au niveau supérieur est appelé père.
Au niveau le plus élevé il y a donc un nœud racine. Au niveau directement inférieur, il y a au plus deux nœuds fils. En continuant à descendre aux niveaux inférieurs, on peut en avoir quatre, puis huit, seize, etc. C'est-à-dire la suite des puissances de deux. Un nœud n'ayant aucun fils est appelé feuille. Le nombre de niveaux total, autrement dit la distance entre la feuille la plus éloignée et la racine, est appelé hauteur de l'arbre.
Le niveau d'un nœud est appelé profondeur.
Les arbres binaires peuvent notamment être utilisés en tant qu'arbre binaire de recherche ou en tant que tas binaire.


Arbre binaire de recherche:

En informatique, un arbre binaire de recherche (ABR) est un arbre binaire dans lequel chaque nœud possède une clé, telle que chaque nœud du sous-arbre gauche ait une clé inférieure ou égale à celle du nœud considéré, et que chaque nœud du sous-arbre droit possède une clé supérieure ou égale à celle-ci — selon la mise en œuvre de l'ABR, on pourra interdire ou non des clés de valeur égale. Les nœuds que l'on ajoute deviennent des feuilles de l'arbre.

Recherche :
La recherche dans un arbre binaire d'un nœud ayant une clé particulière est un procédé récursif. On commence par examiner la racine. Si sa clé est la clé recherchée, l'algorithme termine et renvoie la racine. Si elle est strictement inférieure, alors elle est dans le sous-arbre droit, sur lequel on effectue alors récursivement la recherche. De même si la clé de la racine est strictement supérieure à la clé recherchée la recherche continue sur le sous-arbre gauche. Si on atteint une feuille dont la clé n'est pas celle recherchée, on sait alors que la clé recherchée n'appartient à aucun nœud. On peut la comparer avec la recherche par dichotomie qui procède à peu près de la même manière sauf qu'elle accède directement à chaque élément d'un tableau au lieu de suivre des liens.
Cette opération requiert un temps en O(log(n)) dans le cas moyen, mais O(n) dans le cas critique où l'arbre est complètement déséquilibré et ressemble à une liste chaînée.


Insertion

L'insertion d'un nœud commence par une recherche : on cherche la clé du nœud à insérer ; lorsqu'on arrive à une feuille, on ajoute le nœud comme fils de la feuille en comparant sa clé à celle de la feuille : si elle est inférieure, le nouveau nœud sera à gauche ; sinon il sera à droite.
La complexité est évidemment la même que pour la recherche : O(ln n) dans le cas moyen et O(n) dans le cas critique.

Suppression

Plusieurs cas sont à considérer, une fois que le nœud à supprimer a été trouvé à partir de sa clé :
• Suppression d'une feuille : Il suffit de l'enlever de l'arbre vu qu'elle n'a pas de fils.
• Suppression d'un nœud avec un enfant : Il faut l'enlever de l'arbre en le remplaçant par son fils.
• Suppression d'un nœud avec deux enfants : Supposons que le nœud à supprimer soit appelé N (le nœud de valeur 7 dans le graphique ci-dessous). On le remplace alors par son successeur le plus proche (le nœud le plus à gauche du sous-arbre droit - ci-dessous, le nœud de valeur 9) ou son plus proche prédécesseur (le nœud le plus à droite du sous-arbre gauche - ci-dessous, le nœud de valeur 6). Cela permet de garder une structure d'arbre binaire de recherche. Puis on applique à nouveau la procédure de suppression à N, qui est maintenant une feuille ou un nœud avec un seul fils.

Pour une implémentation efficace, il est déconseillé d'utiliser uniquement le successeur ou le prédécesseur car cela contribue à déséquilibrer l'arbre.
Dans tous les cas cette opération requiert de parcourir l'arbre de la racine jusqu'à une feuille : le temps d'exécution est donc proportionnel à la profondeur de l'arbre qui vaut n dans le pire des cas, d'où une complexité maximale en O(n).

Parcours ordonné

On peut facilement récupérer les éléments d'un arbre binaire de recherche dans l'ordre de leurs clés en parcourant récursivement le sous-arbre gauche, puis en ajoutant la racine, puis en parcourant récursivement le sous-arbre droit. On peut évidemment le faire dans l'ordre inverse en commençant par le sous-arbre droit.
Le parcours de l'arbre se fait en O(n), puisqu'il doit passer par chaque nœud.

C'est de Wikipédia. Ca peut vous être utile.
avatar
L'alchimiste

Messages : 65
Date d'inscription : 06/01/2009
Age : 29

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: Arbre binaire

Message  dellC le Sam 6 Juin - 18:34

Napo a écrit:j'ai une petite question sur 2 fonctions --> ORIG( List edge) et DEST(List edge)
Quelqu'un pourrait m'expliquer ce qu'elle font exactement svp?

Je remarque que je n'ai rien par rapport aux Graphes dans mes notes ... Je découvre donc ça maintenant dans les powerpoint.
Et j'en déduis que c'est dans le cas d'un graphe dirigé (ou les arcs ne sont que dans un sens), pour savoir l'origine et la destination de celui-ci ... Mais ceci n'est qu'hypothèse.
avatar
dellC

Messages : 120
Date d'inscription : 07/11/2008
Age : 29
Localisation : Herve

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: Arbre binaire

Message  L'alchimiste le Sam 6 Juin - 19:09

Napo a écrit:j'ai une petite question sur 2 fonctions --> ORIG( List edge) et DEST(List edge)
Quelqu'un pourrait m'expliquer ce qu'elle font exactement svp?

oui cest bien desinaion et l'origine. Prend en paramètre un arc
avatar
L'alchimiste

Messages : 65
Date d'inscription : 06/01/2009
Age : 29

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: Arbre binaire

Message  Babos le Sam 6 Juin - 19:31

Donc en gros, pour un arc (a,b).

ORIG rendra le sommet A et DEST le somment B ?
avatar
Babos

Messages : 92
Date d'inscription : 19/09/2008
Age : 29

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: Arbre binaire

Message  Napo le Sam 6 Juin - 20:38

Apparemment oui Babos ^^
Merci pour vos réponse ca me semble correcte quand j'y repense :p
avatar
Napo

Messages : 27
Date d'inscription : 07/10/2008
Age : 29
Localisation : Jupille

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: Arbre binaire

Message  Contenu sponsorisé


Contenu sponsorisé


Revenir en haut Aller en bas

Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum