Arbres binaires

Signaler
Messages postés
2
Date d'inscription
lundi 1 décembre 2003
Statut
Membre
Dernière intervention
20 décembre 2003
-
Messages postés
30
Date d'inscription
samedi 4 décembre 2004
Statut
Membre
Dernière intervention
2 avril 2008
-
Bonjour, je suis en train de me taper un tp pour un cours sur les arbres. Dans le code qui suit, la racine redevient null a chaque fois qu'elle sort de la fonction Ajout et je comprends pas trop pourquoi. Surement une histoire de pointeurs mal placés mais je pige pas trop. Si quelqu'un peut m'aider, merci d'avance ! Le reste n'est pas terminé alors n'en tenez pas compte.

#include
#include <conio.h>

/******************************************************************************
Structures
******************************************************************************/

struct Noeud
{
int Valeur;
struct Noeud * Gauche;
struct Noeud * Droite;
};
typedef Noeud * PtrNoeud;

/******************************************************************************
Prototypes
*****************************************************************************/

PtrNoeud CreerNoeud(int Nombre, PtrNoeud Gauche, PtrNoeud Droite);
PtrNoeud CreerFeuille (int Nombre);
void Ajout (int Nombre, PtrNoeud Racine);
void CreerArbre (PtrNoeud Racine);
void AfficherArbre (PtrNoeud Racine, int Col, int Lig);

/*****************************************************************************
main
****************************************************************************/

void main (void)
{
PtrNoeud Ancetre = NULL;
char Reponse;

CreerArbre (&Ancetre);
cout <<"\n\tL'arbre a ete cree.\nDesirez-vous:"
<<"\n\n\t1- Afficher l'arbre ?"
<<"\n\t2- Le parcourir en ordre infixe ?"
<<"\n\t3- Le parcourir en ordre prefixe ?"
<<"\n\t4- Effectuer une recherche dans l'arbre ?"
<<"\n\t5- Supprimer un element de l'arbre ?"
<<"\n\n\tEntrez votre reponse: ";
cout <Valeur;
getch();
//AfficherArbre (Ancetre, 39, 3);
getch();
}

PtrNoeud CreerNoeud(int Nombre, PtrNoeud Gauche, PtrNoeud Droite)
{
PtrNoeud Nouveau;
Nouveau = new(Noeud);
Nouveau->Valeur = Nombre;
Nouveau->Gauche = Gauche;
Nouveau->Droite = Gauche;
return Nouveau;
}

PtrNoeud CreerFeuille (int Nombre)
{
return CreerNoeud(Nombre,NULL,NULL);
}

void Ajout (int Nombre, PtrNoeud Racine)
{
if (Racine == NULL)
{
Racine = CreerFeuille(Nombre);
}
else
{
if (Nombre > &Racine->Valeur)
{
if (Racine->Droite==NULL)
{
Racine->Droite = new(Noeud);
Racine->Droite=CreerFeuille(Nombre);
}
else
{
Ajout(Nombre, &Racine->Droite);
}
}
else
{
if (Racine->Gauche==NULL)
{
Racine->Droite = new(Noeud);
Racine->Gauche=CreerFeuille(Nombre);
}
else
{
Ajout(Nombre, Racine->Gauche);
}
}
}
}

void CreerArbre (PtrNoeud Racine)

{
int Nombre;
int Col = 28;
char Reponse = 'O';

cout <<"CREATION DE L'ARBRE";
while (Reponse == 'O')
{
gotoxy (1,24);
clreol();
gotoxy (1,25);
clreol();
gotoxy (1,24);
cout <<"Entrez un nombre de 0 a 99: ";
cin >> Nombre;
if (Nombre <0 || Nombre >99)
{
cout <<"Le nombre doit etre entre 0 et 99";
getch();
gotoxy(1,25);
clreol();
}
else
{
Ajout (Nombre, Racine);
gotoxy (1,3);
cout << "Voici les nombres choisis: ";
gotoxy (Col,3);
cout<<Nombre;
Col += 3;
}
gotoxy (1,25);
cout <<"Desirez-vous entrer un autre nombre ? (O ou N) ";
Reponse = getche();
Reponse = toupper(Reponse);
}

}

void AfficherArbre (PtrNoeud Racine, int Col, int Lig)
{

gotoxy (Col,Lig);
cout <<Racine->Valeur;
if (Racine->Gauche)
{
Col-=5;
Lig+=5;
AfficherArbre(Racine->Gauche,Col,Lig);
}
else if (Racine->Droite)
{
Col+=5;
Lig+=5;
AfficherArbre(Racine->Droite,Col,Lig);
}
}

4 réponses

Messages postés
2070
Date d'inscription
mardi 22 avril 2003
Statut
Membre
Dernière intervention
3 juillet 2006
8
dans créer noeud :

lors de l'insertion du nouveau noeud entre gauche et droite et il faut égaement mettre à jour gauche et droite :

Nouveau->Valeur = Nombre;
Nouveau->Gauche = Gauche;
Nouveau->Droite = Gauche;

if(Gauche)
Gauche->Droite = Nouveau;
if(Droite)
Droite->Gauche = Nouveau;

sinon tu ne pourras pas parcourris correctement l'arbre
Messages postés
2
Date d'inscription
lundi 1 décembre 2003
Statut
Membre
Dernière intervention
20 décembre 2003

t'as raison, merci, c'est en effet un erreur a modifier. Ca m'évitera un futur déboguage. Toutefois le probleme reste toujours la. La fontcion CreerNoeud ne recoit que des feuille lors de la création de l'arbre. Et la fonction Ajout me renvoit toujours Racine==Null. Un pointeur n'est-il pas global par défaut ?
Messages postés
171
Date d'inscription
jeudi 30 janvier 2003
Statut
Membre
Dernière intervention
20 juillet 2008

Un pointeur n'est pas global par defaut. Un pointeur est une "variable" qui contient comme valeur l'adresse memoire du debut d'un espace memoire reservé par le systeme d'exploitation a votre application.

Comme tout variable local, le pointeur est eliminé a la sortie d'une fonction par exemple.

Toutefois, les espaces memoires alloué a votre application demeure a votre application.

Donc si vous reservez un espace memoire et que localement vous avez un pointeur qui garde son adresse tout est beau. Ensuite, si le pointeur est eliminé, l'espace memoire est reservez quand meme mais n'est plus recuperable. C'est pourquoi il faut attacher l'adresse de cette espace memoire a une structure "globale".

C'est le principe des listes chainées et des arbres binaires entre autre.

Mais en aucun cas, un pointeur n'est automatiquement globale...

http://www.joepatent.comJoe Patent
Messages postés
30
Date d'inscription
samedi 4 décembre 2004
Statut
Membre
Dernière intervention
2 avril 2008

Tu aurais pu faire ta fonction CreerNoeud( )sans argument et avec un parametre void (parfois c mieux) et ensuite tu exploites ta fonction ajout qui va t'inserer un Noeud de façon dynamique...Ouh en bref Voici un exple de code..

Struct Noeud
{
Noeud * pere;
Noeud * gauche;
Noeud * droite;
int Val;
};
class Arbr_bin
{
public:
Noeud * Racine; //declarer Racine globale pr 1 utilisat° + simple
Arbr_bin(); // mettre Racine =NULL;
~Arbr_bin( );
/* j'ai la flemme ainsi de suite... lol tu ajoutes les proto des tes fct° */

};

Noeud* Arb_bin::Ajout(int data, Noeud * courant)
{
if (!courant)
{
courant=new( Noeud);
courant->Val=data;
courant->gauche=courant->droite=courant->pere =NULL;
else
{
if(courant->Val > data)
{
courant->gauche = Ajout(data,courant->gauche);
courant->SAG ->pere = courant;
/*il me semble q c'est l'initialisation dont te parlais ymca2003 pr q la racine s'implemente automatiquement !!! */
}
else
{
courant->droite = Ajout(data,courant->droite);
courant->droite->pere = courant;
}
}
return courant;
}

void Arb_bin::CreerNoeud( )

{
char rep;
int data;
do
{
cout<<" valeur pour la racine : "; cin>>data;
Racine=InsererNoeud(data,Racine); /* racine de ton arbre est crée avec une valeur dedans */
cout<<"Creer un autre noeud? O/N : "; cin>>rep;
}
while((rep=='o') || (rep=='O'));
}

Ton arbre est crée avec les valeur dedans,maintenant à toi de jouer pr le reste...
C'est pas une solution à ton pb(loin de là ) c'est juste pr te proposer une autre façon de voir la chose parce que moi aussi j'ai eu ce genre de pb au depart... lol