Discussion :

[Gryzzly]

Bonjour,

J'aurais besoin d'aide concernant ceci.
J'ai créer une fonction qui construit un arbre contenant des opérateurs,des constantes et des variables.

Les variables peuvent avoir une valeur représenté par un arbre.

Par exemple:
pour un parametre donné par exemple x , je lui attribue une valeur représenté par un arbre par exemple

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

x -> + * 3 7 x

je dois remplacer toutes les occurences de x dans l'arbre.
Par exemple si mon arbre est :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
                       --------+--------                                                             
                        |                     |                                                           
                   ----*----               x                                                            
                 |            |                                                                           
                x             8

le nouvel arbre doit etre le suivant:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
                                 ----------+----------                                               
                                 |                          |                                            
                           ----*----                ----+-----                                      
                          |            |              |            |                                     
                      ---+---         8        ---*---        x                                    
                      |        |                  |         |                                           
                   --*--      x                 3         7                                          
                   |      |                                                                                                            
                   3       7

Est ce que quelqu'un aurait une manière da faire à m'indiquer?


Merci d'avance

[Zenol]

Bon, je suis null en algorithme, mais ne sufirais-t'il pas de parcoyurir l'arbre et pour chaque X rencoutrer, le remplacer par la copie dde l'arbre de remplacemenet?

[Gryzzly]

Bon, je suis null en algorithme, mais ne sufirais-t'il pas de parcoyurir l'arbre et pour chaque X rencoutrer, le remplacer par la copie dde l'arbre de remplacemenet?

Bonjour,

est ce que tu pourrais m'écrire en pseudo code ,la manière dont tu coderais cela.

Merci d'avance

[xxiemeciel]

Salut

comme l'a dit JC_Master, il suffit de parcourir ton arbre et de remplacer les noeuds contenant X par l'arbre représentatn le nouveau X

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
 
//La fonction change s'applique sur un noeud this (au depart la tete de ton arbre)
change(Noeud this, Valeur X,Noeud NewX)
{
     Si this == NULL return;
 
     Si  this->valeur == X 
     alors 
              this->Valeur = NewX->Valeur
              this->FilsDroit = NewX->FilsDroit
              this->FilsGauche = NewX->FilsGauche
     Sinon
              change(this->FilsDroit,X,NewX)
              change(this->FilsGauche,X,NewX)
}

XXiemeciel

[doccpu]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//La fonction change s'applique sur un noeud this (au depart la tete de ton arbre)
change(Noeud this, Valeur X,Noeud NewX)
{
     Si this == NULL return;
 
     Si  this->valeur == X 
     alors 
              this->Valeur = NewX->Valeur
              this->FilsDroit = NewX->FilsDroit
              this->FilsGauche = NewX->FilsGauche
     Sinon
              change(this->FilsDroit,X,NewX)
              change(this->FilsGauche,X,NewX)
}

return prend des resources !

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
change(Noeud this, Valeur X,Noeud NewX)
{
     Si this != NULL 
     alors
            Si  this->valeur == X 
            alors 
                   this->Valeur = NewX->Valeur
                   this->FilsDroit = NewX->FilsDroit
                   this->FilsGauche = NewX->FilsGauche
            Sinon
                    change(this->FilsDroit,X,NewX)
                    change(this->FilsGauche,X,NewX)
            FinSi
     FinSi
}

[Gryzzly]

Salut

comme l'a dit JC_Master, il suffit de parcourir ton arbre et de remplacer les noeuds contenant X par l'arbre représentatn le nouveau X

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
 
//La fonction change s'applique sur un noeud this (au depart la tete de ton arbre)
change(Noeud this, Valeur X,Noeud NewX)
{
     Si this == NULL return;
 
     Si  this->valeur == X 
     alors 
              this->Valeur = NewX->Valeur
              this->FilsDroit = NewX->FilsDroit
              this->FilsGauche = NewX->FilsGauche
     Sinon
              change(this->FilsDroit,X,NewX)
              change(this->FilsGauche,X,NewX)
}

XXiemeciel

Bonjour,

merci de ta réponse.
J'ai une question à propos du pseudo-code.
Est ce que la fonction que tu as écrit change toutes les occurences de Valeur ?
J'ai l'impression qu'une fois qu'elle a trouvé la valeur la fonction fait le changement puis la fonction s'arrete mais ne fais pas cela pour les autres.

[xxiemeciel]

merci de ta réponse.
J'ai une question à propos du pseudo-code.
Est ce que la fonction que tu as écrit change toutes les occurences de Valeur ?
J'ai l'impression qu'une fois qu'elle a trouvé la valeur la fonction fait le changement puis la fonction s'arrete mais ne fais pas cela pour les autres.

C'est une fonction recursive elle passe dans tout les noeud et change toutes les occurences de X dans l'arbre par NewX. Je te suggere de lire les cours de developpez sur le sujet.

Moi je prend l'avion pour l'Europe dans quelques heures je ne pourrais donc pas continuer cette discussion. Mais je suis sur que d'autres personnes t'aideront si tu as des problemes.

XXiemeciel

[xxiemeciel]

return prend des resources !

je ne crois pas non, tout depend du langage ... En l'occurence en C++ return peut servir a terminer une fonction void.

XXiemeciel

[Gryzzly]

Bonjour,

Voici le code en C qui répondait à la question que j'ai posé.
J'ai un problème avec les return car il sont mal placés.
De plus ,faut'il que je mette *racine =... pour la récursion?
Merci de me corriger

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Arbre Modif(Arbre *racine, char X, Arbre Nouveau)
{
  if(*racine == NULL) return NULL;
 
  if((*racine)->lettre == X)
    {
      (*racine)->lettre = Nouveau->lettre;
      (*racine)->gauche = Nouveau->gauche;
      (*racine)->droit = Nouveau->droit;
    }
  else
    {
      *racine = Modif(&((*racine)->gauche),X,Nouveau);
      *racine = Modif(&((*racine)->droit),X,Nouveau);
    } 
  return (*racine);
}

[Zenol]

Déja, pourquoi tu précède ta variable dynamique d'un *?
Et si tu le fait, alors tu doit utiliser . au lieu de -> non?
Enfin, pas de return Racine ou return NULL
Ta fonction est une fonction void, qui modifier l'objet en paramêttre, et non qui en créé un nouveau. Il faut bien penser que ta fonction s'apelle elle même.
Enfin, pour terminer, pas de racine = change, seulement un change avec les paramêtres. VOici un code coriger(pas tester )

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
void Modif(Arbre *racine, char X, Arbre Nouveau)
{
  if(racine == NULL) return;
 
  if(racine->lettre == X)
    {
      racine->lettre = Nouveau.lettre;
      racine->gauche = Nouveau.gauche;
      racine->droit = Nouveau.droit;
    }
  else
    {
     //Si gauche et droite est un arbre dinamique, on remplace & par &*
      Modif(&(racine->gauche),X,Nouveau);
      Modif(&(racine->droit),X,Nouveau);
    }
}
 
//Call :
Arbre Link;
Arbre Change;
Modif(&Link,Change);
 
//Call :
Arbre *Link;
Arbre *Change;
Modif(&*Link,*Change);

[Gryzzly]

Déja, pourquoi tu précède ta variable dynamique d'un *?
Et si tu le fait, alors tu doit utiliser . au lieu de -> non?
Enfin, pas de return Racine ou return NULL
Ta fonction est une fonction void, qui modifier l'objet en paramêttre, et non qui en créé un nouveau. Il faut bien penser que ta fonction s'apelle elle même.
Enfin, pour terminer, pas de racine = change, seulement un change avec les paramêtres. VOici un code coriger(pas tester )

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
void Modif(Arbre *racine, char X, Arbre Nouveau)
{
  if(racine == NULL) return;
 
  if(racine->lettre == X)
    {
      racine->lettre = Nouveau.lettre;
      racine->gauche = Nouveau.gauche;
      racine->droit = Nouveau.droit;
    }
  else
    {
     //Si gauche et droite est un arbre dinamique, on remplace & par &*
      racine = Modif(&(racine->gauche),X,Nouveau);
      racine = Modif(&(racine->droit),X,Nouveau);
    }
}
 
//Call :
Arbre Link;
Arbre Change;
Modif(&Link,Change);
 
//Call :
Arbre *Link;
Arbre *Change;
Modif(&*Link,*Change);

Je souhaite que la fonction me renvoye l'arbre modifié pour l'utiliser dans une fonction.

J'ai mis un * dans Arbre *racine car la racine peut etre modifié.

Est ce que tu pourrais m'indiquer ou doivent etre placé les return

Merci

[Zenol]

En bvoilan modifier cette fonction, te ne feras que la rendre plus compliquer et moin performante, la meilleur solution est de créer une deuxième fonction :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
Arbre CopyModified(Arbre racine, Arbre Nouveau)
{
  //On copie la racine
  Arbre Copy = racine;
  //On modifie la copie
  Modif(&Copy,Nouveau);
  //On renvoi la copie
  return Copy;
}

Sinon je te demendais pourquoi tu déréférencais a chaque fois ton pointeur vers la racine, et pourquoi tu continuais a le manipuler comme un pointeur.
Il faut savoir que Arbre * Branche peut être utiliser soit comme sa : Branche->Feuille ou (*Branche).feuille
Voila, je pensse que mentenant c'est bon.

[fearyourself]

Il faut savoir que Arbre * Branche peut être utiliser soit comme sa : Branche->Feuille ou (*Branche).feuille

A mon avis, il doit avoir quelque chose du style:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
typedef struct sarbre
{
....
}*Arbre;

D'où le fait que (*racine) nécessite une flèche... Mais c'est un problème de C à ce moment là...

Par contre, j'aurais une tendance à faire ceci (en fait j'ai simplement suivi l'algo du dessus, ce que tu n'as pas vraiment fait):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
void Modif(Arbre racine, char X, Arbre Nouveau)
{
  if(racine == NULL) return NULL;
 
  if(racine->lettre == X)
    {
      racine->lettre = Nouveau->lettre;
      racine->gauche = Nouveau->gauche;
      racine->droit = Nouveau->droit;
      }
  else
    {
      Modif(racine->gauche,X,Nouveau);
      Modif(racine->droit,X,Nouveau);
    }
}

Fais attention par contre au fait que ton arbre Nouveau n'est en mémoire qu'une seule fois donc tout modification de l'arbre nouveau aura une répercussion sur tout l'arbre (ceci est pas mal dans le sens où une seule évaluation est nécessaire

Par contre, fait attention, vu que tu codes en C, à la déallocation, il faudra faire un seul free sur l'arbre Nouveau et là, ça devient plus complexe...

Jc

[Zenol]

Désoler pour le = qui trainais, j'ai oublier de l'éffacer ^^
Sinon, ma fonction fonctione par copie si Nouveau est statique.