Informatique

Salut les quilles

Alors voilà je débute en C et je dois réaliser une fonction qui compte le nombre de noeud et le nombre de feuille d'un arbre binaire.

Mon programme est composé d'une fonction main, fonction qui fait appel à la fonction de comptage analyse_arbre.

Mon problème est le suivant : la fonction analyse_arbre est une fonction de type void et prend en entrée deux pointeurs de type int : nb_feuille et nb_noeud, qui sont des références sur des variables de types int déclarées dans la fonction main juste avant l'exécution de la fonction de comptage.
Il est précisé que les variables ainsi déclarées doivent cependant être initialisées par la fonction analyse_arbre, en effet la récursion de ma fonction incrémente la valeur désignée par le pointeur, la voici :

 void analyse_arbre( racine, nb_feuille, nb_noeud ) {

 // Il faudrait que je puisse initialiser les valeurs pointées à 0 lors du comptage du premier noeud (ou racine), sans pour autant attribuer 0 à chaque récursion au risque de perdre les informations obtenues par la fonction appelante. J'ai compris que des valeurs arbitraires étaient attribuées à des valeurs déclarées sans initialisation.


// Si l'arbre est vide, la fonction ne modifie pas les valeurs d'entrée

   if (!(racine==NULL)) {

 // la fonction ne récursionne pas lorsqu'elle trouve une feuille

      if ((racine->droit == NULL)||(racine->gauche == NULL)) { 

         *nb_feuille += 1

         ;
      }

      else {

         *nb_noeud += 1; // Si on ne tombe pas sur une feuille, alors c'est un noeud

         //on récursionne sur les cellules filles
         analyse_arbre(racine->droit, nb_feuille, nb_noeud); 
         analyse_arbre(racine->gauche, nb_feuille, nb_noeud);
      };

      

   };

}

J'ai essayé d'exposer le problème le plus clairement possible, sachant que je débute en C.. un khey d'humeur altruiste ?

Merci de m'avoir lu.

Je vois pas comment tu peux faire la différence entre la racine de l'arbre et n'importe quel autre nœud dans analyse_arbre. Ce que tu peux faire c'est une fonction qui initialise les deux pointeurs, puis lance analyse_arbre avec la racine.

void analyse_arbre_start(racine, nb_feuille, nb_noeud ) {
    *nb_feuille = 0;
    *nb_noeud = 0;
    analyse_arbre(racine, nb_feuille, nb_noeud);
}

Et pour les feuilles ta condition devrait avoir et ET et pas ou. Les deux enfants sont null sur une feuille.

OK, il y a deux conventions differentes en fonction de ce que tu veux que ta fonction fasse:

1/ tu supposes que nb_feuille n'est pas initialise particulierement et qu'a la fin de la fonction, nb_feuille doit contenir exactement le nombre de feuille de ce sous arbres. Si c'est ca que tu suppose alors tu ne peux pas utilise qu'une seule valeur de nb_feuille quand tu fais l'appel recursif parceque l'arbre de gauche va ecraser la valeur de l'arbre de droite. Et donc tu auras besoin de deux variables differente pour stocker les comptes a gauche et les comptes a droite.

2/ tu suppose que la fonction n'est pas responsable pour initialise la variable, et elle ne fait qu'incrementer la variable par le nombre de feuille qu'elle trouve. Et dans ce cas tu suppose que la fonction appelante a initialiser le compte correctement (ie., main a initialise a 0)

Personnellement, je pense que 1/ a une semantique plus propre. Donc c'est ca que je ferrais. Mais ca utilise un peu plus de memoire dans la call stack.

Le 01 décembre 2021 à 00:25:57 :
OK, il y a deux conventions differentes en fonction de ce que tu veux que ta fonction fasse:

1/ tu supposes que nb_feuille n'est pas initialise particulierement et qu'a la fin de la fonction, nb_feuille doit contenir exactement le nombre de feuille de ce sous arbres. Si c'est ca que tu suppose alors tu ne peux pas utilise qu'une seule valeur de nb_feuille quand tu fais l'appel recursif parceque l'arbre de gauche va ecraser la valeur de l'arbre de droite. Et donc tu auras besoin de deux variables differente pour stocker les comptes a gauche et les comptes a droite.

2/ tu suppose que la fonction n'est pas responsable pour initialise la variable, et elle ne fait qu'incrementer la variable par le nombre de feuille qu'elle trouve. Et dans ce cas tu suppose que la fonction appelante a initialiser le compte correctement (ie., main a initialise a 0)

Personnellement, je pense que 1/ a une semantique plus propre. Donc c'est ca que je ferrais. Mais ca utilise un peu plus de memoire dans la call stack.

Comment ça le nb de feuille de l'arbre de gauche va écraser le nb de feuilles de l'arbre droit ?

Merci beaucoup pour vos réponses !

Faut pas se dire que ta fonction va modifier des variables pré-existantes. Ici moralement ta fonction prend en entrée un arbre et renvoie deux entiers, "nb_feuilles" et "nb_noeuds".

Sauf que comme en C on ne peut pas directement renvoyer plusieurs valeurs, on simule ça en mettant des pointeurs en arguments dans lesquels la fonction va stocker son résultat.

Donc, dans le cas de l'arbre vide, ta fonction doit stocker la valeur 0 dans les deux pointeurs. C'est là que tes variables vont être « initialisées », plus ou moins.

Ensuite à chaque appel récursif il faudra copier la réponse qui se trouve dans les variables, avant de faire l'appel récursif suivant

Ca serait mieux avec l'énoncé initial plutôt que ton interprétation potentiellement fausse de l'énoncé.

Il faudrait que je puisse initialiser les valeurs pointées à 0 lors du comptage du premier noeud (ou racine), sans pour autant attribuer 0 à chaque récursion au risque de perdre les informations obtenues par la fonction appelante. J'ai compris que des valeurs arbitraires étaient attribuées à des valeurs déclarées sans initialisation.

C'est bizarre et pas clair.

tu t'attends à faire

Arbre racine;
// ... remplissage de l'arbre

int nb_noeud, nb_feuille;

analyse(&racine, &nb_noeud, &nb_feuille);

?

Un collègue qui écrirait ça se prendrait une claque sur la nuque.

Golem2fer, pourquoi? Ca m'a l'air d'etre ne convention raisonnable? Ou j'ai loupe quelquechose?

J'aurais écrit

int nb_noeud = 0;
int nb_feuille = 0;

Bah ca depend du comportement de la fonction analyse. Si analyse ecrit la variable proprement, ca ne sert a rien de l'initialiser.

Que tu fasse:
int a; scanf ("%d), &a);

ou

int a = 0;
scanf ("%d), &a);

Ca ne change absolument rien (en supposant que tu traite le retour de scanf correctement.)

Idée à la noix, utiliser une variable entière static liée à ta fonction récursive qui va permettre de connaître la profondeur à chaque récursion, et ainsi de savoir si on est à profondeur p = 0 pour initialiser les variables ? si je ne fais pas d'erreur, ça devrait fonctionner

Après, est-ce que c'est propre et conventionnel ? A voir.

Le 02 décembre 2021 à 18:05:01 godrik a écrit :
Bah ca depend du comportement de la fonction analyse. Si analyse ecrit la variable proprement, ca ne sert a rien de l'initialiser.

Que tu fasse:
int a; scanf ("%d), &a);

ou

int a = 0;
scanf ("%d), &a);

Ca ne change absolument rien (en supposant que tu traite le retour de scanf correctement.)

Tu peux avoir des variables non-initialisées partout, mais c'est une meilleure pratique de les initialiser. Ca évite les comportements indéfinis.