Arbres binaires

Question

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 /****************************************************************************** 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 <<" L'arbre a ete cree. Desirez-vous:" <<" 1- Afficher l'arbre ?" <<" 2- Le parcourir en ordre infixe ?" <<" 3- Le parcourir en ordre prefixe ?" <<" 4- Effectuer une recherche dans l'arbre ?" <<" 5- Supprimer un element de l'arbre ?" <<" Entrez votre reponse: "; cout 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<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); } }

ymca2003 · Answer

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

His_Dudeness · Answer

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 ?

JoePatent · Answer

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

pmbala · Answer

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

Arbres binaires

4 réponses

Votre réponse

Discussions similaires