Les Allergies
Alimentaires
Posez votre question Signaler

Langage C : recursivité et arbre binaire

Alex739 - Dernière réponse le 28 févr. 2009 à 10:08
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.
Lire la suite 

Langage C : recursivité et arbre binaire »

2 réponses
Réponse
+4
moins plus
velocity 223Messages postés 14 juillet 2008Date d'inscription 27 févr. 2009 à 21:32
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) );
     }
}

Ajouter un commentaire
Ajouter un commentaire
Réponse
+0
moins plus
Alex789 28 févr. 2009 à 10:08
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.

 Ajouter un commentaire
Ajouter un commentaire
Posez votre question
Ce document intitulé « Langage C : recursivité et arbre binaire » issu de CommentCaMarche (www.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.
Dossier à la une
Passage au tout numérique : quel coût pour les particuliers ?