Langage C : recursivité et arbre binaire Fermé

Question

Bonjour,

Voilà je suis en train d'apprendre la recursivité et j'ai quelques problèmes.
J'aimerai faire une fonction qui calcul approximativement la taille d'un arbre.
Je dit approximativement parce que le nombre exacte importe peu vu que je ferai appel à cette fonction pour calculer la taille de deux arbres et savoir qui est le plus grand. 
Voici ce que je propose mais j'ai du mal à savoir si sa peut fonctionner. Je ne peux pas tester pour le moment le code sur machine. Dite moi ce que vous pensez de mon code : Ps on envoie 0 pour le compteur.

int Taille_arbre ( Noeud *racine , int compteur)
{
	if( racine != NULL )
	{
		compteur = compteur + 1;
		compteur = Taille_arbre( racine->fils_G , compteur);
		compteur = Taille_arbre( racine->fils_D , compteur);
	}
	return compteur;
}

Merci d'avance pour vos réponses.

velocity · Accepted Answer

ta fonction retourne un int comme elle le doit, alors pense du cas ou l'arbre vaut NULL , elle ne retourne rien ? ça te retounera un warning pas très grave mais c'est mieux de le mettre.

voici l'algorithme général d'une fonction récursive :
      type_retour   fonction(type_param param) {
                if( condition d'arrêt ){
                         traitement1 ;
                }else if (condition ) {  
                         traitement2 ;
                }else{
                         traitement3 ;
                }
      }

if (!racine) return 0;

je te propose ce code, j'ai pas compilé mais je pense qu'il ca marche :

 int Taille_arbre(Noeud *racine){   //pas besoin de mettre compteur en paramètre,
      if(!racine)
            return 0;
      else{         //ici le noeud existe donc ca compte pour un 1
            return (1+Taille_arbre(racine->gauche)+Taille_arbre(racine->droite) );
     }
}

Alex789 · Answer

Merci. Je ne connaissais pas la structure type pour une fonction recursive. La ligne qui suit le else est également trés intéressante je n'y avais pas pensé. 
Si la racine était NULL dans mon ancien programme, la fonction aurait simplement retourné le compteur que l'on aurait passé en paramètre. Mais je trouve ta solution beaucoup plus intéressante.
Merci pour ton aide, je pense que je vais pouvoir continuer mon programme.

Langage C : recursivité et arbre binaire

2 réponses

Discussions similaires