Insertion d'une occurence dans un arbre

Version imprimable

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:

x -> + * 3 7 x

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

Code:

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

le nouvel arbre doit etre le suivant:

Code:

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

17/12/2005, 13h44
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?
17/12/2005, 14h19
Gryzzly

Citation:

Envoyé par JC_Master

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

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:

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

Citation:

Envoyé par xxiemeciel

Code:

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)
}

:vomi: return prend des resources !

Code:

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
}

Citation:
Envoyé par 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:

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.

18/12/2005, 15h23
xxiemeciel

Citation:

Envoyé par Gryzzly

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
18/12/2005, 15h25
xxiemeciel

Citation:

Envoyé par doccpu

:vomi: 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

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:

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);
}

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 :D)
Code:

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);

Citation:
Envoyé par JC_Master
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 :D)
Code:

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

19/12/2005, 14h20
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:

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.

Citation:

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:

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:

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

19/12/2005, 15h52
Zenol

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