Petit problème pour créer un arbre binaire

Question

Bonjour j'ai un travail à faire pour l'école, il faut que je crée un arbre binaire à partir d'un fichier, comme un arbre généalogique, la racine étant l'enfant, le niveau suivant ce sont les parents, ensuite les grands-parents, etc. Je n'arrive pas à créer l'arbre, chaque fois que j'ajoute un noeud, ma racine change de valeur et je ne comprends vraiment pas pourquoi. Voici mon code source, si vous pouviez m'aider je vous en serait très reconnaissante! //Classe représentant chacun des noeuds class Personne { private : char *NomPersonne; char *PrenomPersonne; Personne *Pere; Personne *Mere; public : Personne(char *Nom, char *Prenom); //constructeur char *GetNom(); //retourne le nom de la personne char *GetPrenom(); //retourne le prénom de la personne void SetPere(Personne *pere); //permet d'ajouter le père void SetMere(Personne *mere); //permet d'ajouter la mère Personne *GetPere(); //retourne le père de la personne Personne *GetMere(); //retourne la mère de la personne }; //variables globales Personne *Racine; Personne *Nouveau; //**************** //*****MAIN****** //**************** void main() { int Choix; char Fichier[50]; char *Nom; char *Prenom; int Niveau; AfficherMenu(); cin>>Choix; Racine = NULL; while (Choix != 8) { switch(Choix) { case 1 : //construire arbre cout<<"Veuillez entrer le nom du fichier a charger"<>Fichier; ConstruireArbre(Fichier); break; } AfficherMenu(); cin>>Choix; } //lorsque les traitements sont terminés, on supprime l'arbre if (Racine != NULL) SupprimerArbre(Racine); } void ConstruireArbre(char *Fichier) { char Nom[30]; char Prenom[30]; ifstream FichierEntree(Fichier); if (!FichierEntree) //si le fichier n'existe pas { cout<<"Erreur lors de l'ouverture du fichier"; } else { Racine = NULL; Nouveau = NULL; int Niveau = 0; while (!FichierEntree.eof()) { for (int i = 0; i < pow(2,Niveau); i++) { FichierEntree>>Nom; FichierEntree>>Prenom; Nouveau = new Personne(Nom, Prenom); Nouveau->SetPere(NULL); Nouveau->SetMere(NULL); char *Chemin = GetChemin(i, Niveau); //la fonction getchemin renvoie un chemin binaire (ex 001), dans ce cas-ci, cela voudrait dire qu'à partir de la racine, on doit se rendre à gauche deux fois, ensuite à droite puis on peut insérer int Index = 0; char Route[50]; strcpy(Route, Chemin); Inserer(Racine, Nouveau, Route, Index); } Niveau++; cout<GetNom(); //c'est avec ca que j'ai pu m'apercevoir que mon arbre ne fonctionnait pas } } } void Inserer(Personne *&Courant, Personne *Nouveau, char Chemin[50], int Index) { if (Courant == NULL) { Racine = Nouveau; } else { if (Courant->GetPere() == NULL) Courant->SetPere(Nouveau); else { if (Courant->GetMere() == NULL) Courant->SetMere(Nouveau); else { if (Chemin[Index] == '0') { Courant = Courant->GetPere(); Inserer(Courant, Nouveau, Chemin, (Index + 1)); } else { Courant = Courant->GetMere(); Inserer(Courant, Nouveau, Chemin, (Index + 1)); } } } } } //Retourne l'endroit où on doit insérer le noeud char *GetChemin(int i, int Niveau) { char buffer[50]; char *Retour; char Zero[50]; itoa (i,buffer,2); int Longueur; Longueur = strlen(buffer); if (Longueur < Niveau) { strcpy(Zero, "0"); for (int j = 0; j < Niveau - Longueur - 1; j++) { strcat(Zero, "0"); } strcat(Zero, buffer); Retour = Zero; return Retour; } Retour = buffer; return Retour; } Je n'ai pas mis tout mon code pour que ce soit moins encombrant, j'espère que c'est quand même compréhensible. Si vous voulez voir mon code au complet, je peux vous en envoyer une copie zippée, je compile avec Microsoft Visual Studio 6.0. Je vous remercie d'avance pour votre aide!

Guillemouze · Answer

void Inserer(Personne *&Courant, Personne *Nouveau, char Chemin[50], int Index)
{
 if (Courant == NULL)
 {
  Racine = Nouveau;
 }
...
if (Chemin[Index] == '0')
    {
     Courant = Courant->GetPere();
     Inserer(Courant, Nouveau, Chemin, (Index + 1));

au premier appel, c ok, Racine prend la valeur Nouveau. mais aux tours suivant, a la premiere iteration de ta fonction recursive, c ok, courant !NULL, mais tu fais des appels recursifs, donc quand tu arrive a une feuille de larbre, Courant NULL, donc tu fixe racine &#224; nouveau, alors que tu devrai pas

au passage tres etrange le *&Courant !!! un pointeru sur une reference :|

dragarth1 · Answer

Oh je vois, merci beaucoup de ton aide, maintenant que je sais ou est le probl&#232;me &#231;a va &#234;tre facile &#224; r&#233;gler!!

Petit problème pour créer un arbre binaire

2 réponses

Votre réponse

Discussions similaires