Créer un arbre binaire complet en C

**derreck** · 08/08/2012, 00h06

J'ai un gros problème!
Je n'arrive pas à créer un arbre binaire complet de telle sorte que tous les noeuds aient exactement deux fils (un fils de droite, un fils de gauche). Voici celui que je propose. Il ne passe que sur l'ordinateur de ma soeur et pas sur le mien (chose que je ne comprends pas non plus).
Merci de m'aider

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
//etablissons la structure de notre arbre binaire
 
typedef struct num
{
       int valeur;
       struct num *fils_gauche;
       struct num *fils_droit;
       }arbre;
 
arbre *creerarbre(arbre *A, int x, int n)
{
      if (A==NULL)
      {
                  A=(arbre*)malloc(sizeof(arbre));//creation de l'arbre
                  A->valeur=x;    //la racine prend une valeur x
                  A->fils_gauche=NULL; //le fils de gauche pointe sur null
                  A->fils_droit=NULL; //le fils de droit pointe sur null
                  n++; //on incrémente le compteur pour atteindre le nombre de niveau souhaité
                  };
      if (n<=7)
      {
             A->fils_gauche=creerarbre(A->fils_gauche,0,n); //on appelle la fonction pour creer le sous arbre ayant le fils de gauche comme racine
             A->fils_droit=creerarbre(A->fils_droit,1,n);//on appelle la fonction pour creer le sous arbre ayant le fils de droit comme racine
               };
      return A;
}
 
void parcoursprefixe(arbre *P)
{
     if(P != 0)
     {
          printf("%d",P->valeur);
          parcoursprefixe(P->fils_gauche);
          parcoursprefixe(P->fils_droit);
          };
}
 
int main()
{ 
      arbre *R;
      R=(arbre*)malloc(sizeof(arbre));
      R=creerarbre(R,0,1);
      parcoursprefixe(R);
      getch();
 
}

**phi1981** · 08/08/2012, 09h13

Ton programme est techniquement juste (ou tout du moins je ne vois pas l'erreur). QQ points toutefois :

- Il est inutile de passer un arbre à la fonction creerarbre(), puisqu'elle se contente d'allouer un noeud et ses descendants.

- De même, le main peut appeler creerarbre() plutot que d'allouer le noeud racine avec malloc(). Ton code sera plus simple.

- parcoursprefixe() devrait produire un retour chariot. Parfois, ne pas produire de retour à la ligne empeche le texte de s'afficher (il attend un flush). De tt façons, juste afficher la valeur des noeuds de l'arbre récursivement va te produire un gros bunch de chiffres illisibles.

Edit : au fait, tu n'as pas dit ce qui ne marchait pas dans ton programme. Quel résultat obtiens tu ?

**diogene** · 08/08/2012, 10h29

Ce programme est faux.
- La ligne n++ est mal placée : elle ne s'exécute que si A == NULL, donc jamais dans le code proposé
- La condition if(A==NULL)... prévoit que l'arbre sera construit à partir de rien. Il est donc inutile de le construire partiellement dans main()
- La fonction ne prévoit pas d'échec du malloc(). C'est une grave lacune pour la fiabilité du code.

Quelques corrections (mais il faut rajouter les tests des malloc()) : Dans ce code, pour vérifier la construction, les valeurs stockées dans les noeux (val1 et val2) sont prévues pour afficher 1,2,3,.... par la fonction parcoursprefixe() à titre de test et devront être changées dans la version définitive.

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
 
#define PROF 7
arbre *creerarbre(arbre *A, int x, int n)
{
      if (A==NULL)
      {
         A=(arbre*)malloc(sizeof(arbre));//creation de l'arbre
         A->valeur=x;    //la racine prend une valeur x
         A->fils_gauche=NULL; //le fils de gauche pointe sur null
         A->fils_droit=NULL; //le fils de droit pointe sur null
      }
      n++; //on incrémente le compteur pour atteindre le nombre de niveau souhaité
      if (n<PROF)
      {
         int val1 = A->valeur+1;               // pour tester
         int val2 = A->valeur+ pow(2,PROF-n);  // pour tester
         A->fils_gauche=creerarbre(A->fils_gauche,val1,n); //on appelle la fonction pour creer le sous arbre ayant le fils de gauche comme racine
         A->fils_droit=creerarbre(A->fils_droit,val2,n);//on appelle la fonction pour creer le sous arbre ayant le fils de droit comme racine
      }
      return A;
}
...
int main(void)
{
      arbre *R;
      R=creerarbre(NULL,1,0);
      parcoursprefixe(R);
      getchar();
      return 0;
}

Maintenant, la logique voudrait que le dernier argument de creerarbre() soit la profondeur de l'arbre que l'on veut créer. Le même code dans cette logique devient :

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
 
arbre *creerarbre(arbre *A, int x, int prof)
{
   if (prof>0)
   {
      int val1;   // pour tester
      int val2;   // pour tester
      if (A==NULL)
      {
         A=malloc(sizeof(arbre));//creation de l'arbre
         A->valeur=x;    //la racine prend une valeur x
         A->fils_gauche=NULL; //le fils de gauche pointe sur null
         A->fils_droit=NULL; //le fils de droit pointe sur null
      }
      val1 = A->valeur+1;               // pour tester
      val2 = A->valeur+ pow(2,prof-1);  // pour tester
      A->fils_gauche=creerarbre(A->fils_gauche,val1,prof-1);
      A->fils_droit=creerarbre(A->fils_droit,val2,prof-1);
   }
   return A;
}
....
int main(void)
{
      arbre *R;
      R=creerarbre(NULL,1,7);
      parcoursprefixe(R);
      getchar();
      return 0;
}

**Hananenounoul** · 21/12/2017, 17h13

mais j comprend pas prk vous avez pas cree la racine d abord j arrive pas a l faire si qlq peut m aider svp et merci

**dalfab** · 22/12/2017, 08h42

Bonjour,

Une règle incontournable du C est qu'une fonction ne peut pas modifier un paramètre passé, le seul moyen est de passer l'adresse d'une donnée et la fonction utilisera ce pointeur pour y mettre quelque chose.

La fonction creerarbre() si elle reçoit un arbre *A, ne pourra utiliser ce A que pour y remplir (ou lire) les 3 champs de l'arbre. Elle ne pourra pas changer le pointeur qu'elle reçoit, elle n'agira que sur ce qui est pointé.
Si on vient de créer un arbre pointé par A, en appelant creerarbre( A->fils_gauche , ..... ), la fonction recevra sa valeur donc NULL, et ne pourra la changer. Donc finalement ce paramètre est toujours NULL dans ton cas comme l'a déjà dit diogene et donc ne sert à rien.
Ici ta fonction reçoit un arbre* et retourne un arbre*, ces 2 possibilités ne font que complexifier la solution. Il faudrait ou bien que la fonction modifie son paramètre ou bien qu'elle fabrique un arbre et retourne un pointeur dessus. Ce qui donne soit void creerarbre(arbre **ptptA , .....) soit arbre* creerarbre( .....). Le premier cas nécessite un pointeur de pointeur qui est un peu lourd pour un débutant, intéressons nous au second.

Le second paramètre x est la valeur à affecter à valeur, ce qui n'a pas beaucoup de sens car plusieurs seront créés, on pourrait faire que cette valeur évolue pour mieux reconnaître les nœuds.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
arbre* creerarbre( int valRacine , int niv ) {
   if ( niv < 0 )
      return NULL;
   arbre*  a = malloc( sizeof *a );
   a->valeur = valRacine;
   int delta = 1 << niv; // les fils gauches et droites auront une valeur dépendant de la profondeur 
   a->fils_gauche = creerarbre( valRacine - delta , niv - 1 );
   a->fils_droite = creerarbre( valRacine + delta , niv - 1);
   return a;
}

**Matt_Houston** · 24/12/2017, 19h28

Et donc, tu comptes développer ? Dans les deux sens du terme..

Après avoir profané le repos éternel de ce fil, tu réponds « j'ai rien pigé » à un exemple complet accompagné d'une quinzaine de lignes explicatives.. T'as pas le sentiment de manquer de respect à ton interlocuteur ? Au bout d'un moment, faut penser à se prendre en main.

**dinobogan** · 26/12/2017, 16h36

Elle ne fonctionne pas, qu'est-ce que cela signifie ? Le compilateur sort des erreurs ? Le programme s'exécute mais plante ? Ou ne sort pas le résultat attendu ?