Probléme sur les arbres.
Utilisateur anonyme
-
philippe -
philippe -
Voilà je cherche en faite à compter la hauteur d’un arbre grâce à fonction suivante :
Int Calcul_Hauteur(ptr_arbre p,int h){
static int hg=0;
static int hd=0;
if(p==NULL)
h=0;
else{
Calcul_Hauteur(p->sag,hg++);
Calcul_Hauteur(p->sad,hd++);
if(hg>hd)
h=hg+1;
else
h=hd+1;
}
}
Mais le problème est que quand je le test sur un arbre il me donne une hauteur erronée, en effet on dirait que le programme ne fait pas de différence entre hg et hd, de plus à chaque fois qu’un nœud est rencontré il y a incrémentation de hg ou de hd.
S’il y a quelqu’un ou plusieurs personnes qui peuvent m’aider je les remercie d’avance.
L'administrateur.
Int Calcul_Hauteur(ptr_arbre p,int h){
static int hg=0;
static int hd=0;
if(p==NULL)
h=0;
else{
Calcul_Hauteur(p->sag,hg++);
Calcul_Hauteur(p->sad,hd++);
if(hg>hd)
h=hg+1;
else
h=hd+1;
}
}
Mais le problème est que quand je le test sur un arbre il me donne une hauteur erronée, en effet on dirait que le programme ne fait pas de différence entre hg et hd, de plus à chaque fois qu’un nœud est rencontré il y a incrémentation de hg ou de hd.
S’il y a quelqu’un ou plusieurs personnes qui peuvent m’aider je les remercie d’avance.
L'administrateur.
A voir également:
- Probléme sur les arbres.
- Arbre généalogique à remplir sur ordinateur gratuit - Télécharger - Généalogie
- Animal crossing wii arbres a clochettes . - Forum Wii
- Pokémon version jaune G.C couper arbres - Forum Jeux vidéo
- Selon la NASA, les arbres peuvent nous prévenir des éruptions de volcans - Guide
- Problème sur arbre généalogique family by ✓ - Forum Loisirs / Divertissements
7 réponses
Evident que hg (ou hd) soit incremente a chq appel puisq c'est toi qui l'incremente ds ton code : calcul_hauteur (a->sag, hg++). Pourqoi ta fct retourne un int alors q tu ne l'utilises pas?
voici un code : cela utilise la definition inductive suivante :
hauteur (a) = 1 + max (hauteur(gauche), hauteur(droite))
hauteur (null) = 0
int max (int n, int m) { return (n > m ? n : m); }
/* je suppose c'est un arbre binaire, vu ton code */
int height (tree a) {
if (a == NULL)
[tab]return 0;
return (1 + max ( height (a->left), height (a->right));
}
tafiscobar "lou waye def bopame"
la nullite n'existe pas, l'ignorance oui, ah je suppose!!!
voici un code : cela utilise la definition inductive suivante :
hauteur (a) = 1 + max (hauteur(gauche), hauteur(droite))
hauteur (null) = 0
int max (int n, int m) { return (n > m ? n : m); }
/* je suppose c'est un arbre binaire, vu ton code */
int height (tree a) {
if (a == NULL)
[tab]return 0;
return (1 + max ( height (a->left), height (a->right));
}
tafiscobar "lou waye def bopame"
la nullite n'existe pas, l'ignorance oui, ah je suppose!!!
Ce que je comprend pas sur ton algo c'est l'endroit où il compte la hauteur (oui je sais tu vas me dire c'est l'appel récursif mais où il y a le decompte??)
L'administrateur.
L'administrateur.
tu ne connais pas la definiton inductive? tu veux la hauteur non? l'appel recursif te le fait, ya pas besoin de compteur, sauf si tu veux le faire en iteratif (et ds ce cas pourqoi rendre difficile quelqe chose qui marche bien?). C'est des appels en cascade, le decompte est fait en remontant ds l'arbre des appels recursifs : avant de retourner, j'attends que mes fils me retournent leur hauteur et ensuite je retourne ma hauteur et ainsi de suite jusqu'a ce que l'on arrive a la racine qui retourne la hauteur de l'arbre.
Je te conseille de le faire tourner a la main sur un exemple et si tu as compris c'est coua un appel recursif, tu verras le decompte.
tafiscobar "lou waye def bopame"
la nullite n'existe pas, l'ignorance oui, ah je suppose!!!
Je te conseille de le faire tourner a la main sur un exemple et si tu as compris c'est coua un appel recursif, tu verras le decompte.
tafiscobar "lou waye def bopame"
la nullite n'existe pas, l'ignorance oui, ah je suppose!!!
salut!
Moi, je ne savais pas que l'on puvait compiler une fonction qui ne retourne rien alors que son prototype indique une valeur retournée...
autrement, en deduction logique, je crois que c'est ce que tu voulais faire d'ailleurs), la profondeur d'un noeud, c'est le plus profond de ces fils + 1
int calculhauteur(pnoeud* courant);
{
/* condition d'arret : pas de fils. profondeur nulle*/
if(courant->filsgauche == NULL && courant->filsdroit == NULL)
return(0);
else
hd = calculhauteur(courant->filsdroit);
hg = calculhauteur(courant->filsgauche);
return(max(hd,hg)+1)
}
normalement, c'est bon. j'ai pas essayé.
Moi, je ne savais pas que l'on puvait compiler une fonction qui ne retourne rien alors que son prototype indique une valeur retournée...
autrement, en deduction logique, je crois que c'est ce que tu voulais faire d'ailleurs), la profondeur d'un noeud, c'est le plus profond de ces fils + 1
int calculhauteur(pnoeud* courant);
{
/* condition d'arret : pas de fils. profondeur nulle*/
if(courant->filsgauche == NULL && courant->filsdroit == NULL)
return(0);
else
hd = calculhauteur(courant->filsdroit);
hg = calculhauteur(courant->filsgauche);
return(max(hd,hg)+1)
}
normalement, c'est bon. j'ai pas essayé.
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
Merci pour ta solution elle fonctionne correctement dans mon application. Je crois en effet que je n'avais pas compris correctement le principe de récursivité....
L'administrateur.
L'administrateur.
Bonjour à tous,je suis en train de travailler sur la manip des arbres binaires,mais là je suis bloqué! Mon progr se compile tres bien,mais lors de l'affichage,il ne m'affiche que la racine... voici mes lignes de codes...
struct Noeud
{ int Val;
Noeud *SAG; //fils gauche
Noeud *SAD; //fils droit
class Arbre_bin
{
public:
Noeud * Root;
/*ttes les fct ci dessous st declarée en ' public : ' y compris le ptr Root */
};
Noeud * Arbre_bin::InsererNoeud(int data,Noeud * courant)
{
if(courant == NULL)
{
courant=new Noeud;
courant->SAG=NULL;
courant->SAD=NULL;
courant->Val=data;
}
else
{
if(courant->Val < data)
{
courant->SAG = InsererNoeud(data,courant->SAD);
}
else
{
courant->SAD = InsererNoeud(data,courant->SAG);
}
}
return NULL;
}
/*** CREER LA RACINE DE L'ARBRE ****/
void Arbre_bin::CreerNoeud( )
{
int data;
char rep;
cout<<"Entrer la valeur dans la racine : "; cin>>data;
Root = InsererNoeud(data,Root);
cout<<"Voulez vous Inserer un autre noeud? O/N "; cin>>rep;
while((rep=='o') || (rep=='O'))
{
cout<<"Entrer la valeur dans ce noeud : "; cin>>data;
InsererNoeud(data,Root);
cout<<Root->Val;
cout<<"Voulez vous Inserer un autre noeud? O/N "; cin>>rep;
}
if((rep=='n') || (rep=='N')) Menu( );
/* Menu( ) est 1 fct pr le choix de la fonction à tester ds le main */
}
int main ( )
{
Arbre_bin Ar ;
int valeur ;
int Choix ;
Choix = Ar.Menu() ; ma fct Menu( ) a 8 choix possibles...
while((Choix < 1)||(Choix > 8))
{
return Ar.Menu();
}
switch (Choix)
{
case 1:
Ar.CreerNoeud( );
Ar.InsererNoeud (valeur,Ar.Root); //Peut etr cè cet appel ki è bad
break;
case 2 : if(Ar.Root == NULL)
{
cout <<"arbre vide!!!"<<endl;
}
else
{
cout<<"AFFICHAGE EN PREORDRE:" <<endl<<endl;
Ar.Afficher_Pre_Ordre(Ar.Root);
}
break;
case 3 : if(Ar.Root == NULL)
{
cout <<"arbre vide!!!"<<endl;
}
else
{
cout<<"AFFICHAGE EN ORDRE : "<< endl;
Ar.Afficher_Ordre(Ar.Root);
}
break;
}
bon j'ai du tronquer le progr,c'est juste pr que vs ayiez une idée
struct Noeud
{ int Val;
Noeud *SAG; //fils gauche
Noeud *SAD; //fils droit
class Arbre_bin
{
public:
Noeud * Root;
/*ttes les fct ci dessous st declarée en ' public : ' y compris le ptr Root */
};
Noeud * Arbre_bin::InsererNoeud(int data,Noeud * courant)
{
if(courant == NULL)
{
courant=new Noeud;
courant->SAG=NULL;
courant->SAD=NULL;
courant->Val=data;
}
else
{
if(courant->Val < data)
{
courant->SAG = InsererNoeud(data,courant->SAD);
}
else
{
courant->SAD = InsererNoeud(data,courant->SAG);
}
}
return NULL;
}
/*** CREER LA RACINE DE L'ARBRE ****/
void Arbre_bin::CreerNoeud( )
{
int data;
char rep;
cout<<"Entrer la valeur dans la racine : "; cin>>data;
Root = InsererNoeud(data,Root);
cout<<"Voulez vous Inserer un autre noeud? O/N "; cin>>rep;
while((rep=='o') || (rep=='O'))
{
cout<<"Entrer la valeur dans ce noeud : "; cin>>data;
InsererNoeud(data,Root);
cout<<Root->Val;
cout<<"Voulez vous Inserer un autre noeud? O/N "; cin>>rep;
}
if((rep=='n') || (rep=='N')) Menu( );
/* Menu( ) est 1 fct pr le choix de la fonction à tester ds le main */
}
int main ( )
{
Arbre_bin Ar ;
int valeur ;
int Choix ;
Choix = Ar.Menu() ; ma fct Menu( ) a 8 choix possibles...
while((Choix < 1)||(Choix > 8))
{
return Ar.Menu();
}
switch (Choix)
{
case 1:
Ar.CreerNoeud( );
Ar.InsererNoeud (valeur,Ar.Root); //Peut etr cè cet appel ki è bad
break;
case 2 : if(Ar.Root == NULL)
{
cout <<"arbre vide!!!"<<endl;
}
else
{
cout<<"AFFICHAGE EN PREORDRE:" <<endl<<endl;
Ar.Afficher_Pre_Ordre(Ar.Root);
}
break;
case 3 : if(Ar.Root == NULL)
{
cout <<"arbre vide!!!"<<endl;
}
else
{
cout<<"AFFICHAGE EN ORDRE : "<< endl;
Ar.Afficher_Ordre(Ar.Root);
}
break;
}
bon j'ai du tronquer le progr,c'est juste pr que vs ayiez une idée
