Discussion :

[jurio]

Bonjour,

Je travaille actuellement sur les arbres ternaires lexicographiques (une sorte d'arbre binaire(principe d'ordre) avec un fils milieu en plus)
Voici la structure :

Code :

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

1
2
3
4
5
6
7
 
 typedef struct noeudT{
	struct noeudT *filsGauche;
	struct noeudT *filsDroit;
	struct noeudT *filsMilieu;
	char val;
}NoeudT,*ArbreT;

Je n'arrive pas du tout à écrire la méthode de suppression d'un mot dans l'arbre... étant donné que des lettres peuvent être utiliser pour un autre mot, je ne peux pas supprimer récursivement chaque lettre de l'arbre en le parcourant car il y a des chances que plusieurs lettres du mots sont utilisées par d'autre mots.... et je risquerai de 'détruire' l'arbre... je sais pas trop comment expliqué tout çà...

Est ce que vous avez un code en langage C de préférence ou meme en algo tout simple qui effectue la suppression d'un mot d'arbre ternaire, je serai super heureux!!

Merci pour votre aide

[PRomu@ld]

Il faut partir d'un raisonnement simple.

Tu n'as plus besoin d'un noeud lorsque ses sous arbres (tous) sont vides après suppression, ainsi, lorsque tu supprimes un mot, tu parcours en profondeur jusqu'à obtenir ton mot en entier (ie. jusqu'à sa dernière lettre), et ensuite tu remonte en regardant si tu dois supprimer ou pas les noeuds.

Une vague idée comme ça (absolument pas testé, donc méfiance) dans un pseudo-dialecte de pseudo langage C

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
29
30
31
 
supprimer_noeud ( noeud * node , char * chaine , bool * a_supprimer)
 
si chaine[0] == '\0' alors 
// Tu es arrivé sur la fin donc tu regardes si tu dois supprimer
     si node->filsGauche == NULL et 
        node->filsMilieu   == NULL et 
        node->filsDroit    == NULL alors
            (*a_supprimer) = true ;
     sinon 
          (*a_supprimer) = false ;
     fin si
sinon
     bool del_fils;
     // Tu recupère dans quel fils se trouve la suite du mot
     bon_fils = quel_fils( node , chaine[0] );  
     supprimer( bon_fils , chaine + 1 , &del_fils ) ;
 
     // Tu vérifie si tu dois supprimer le fils 
     si del_fils == true alors
          free( bon_fils ) ; // N'oublie pas de le mettre à NULL aussi
     fin si    
 
     // Tu vérifie en fin de suppression
     si node->filsGauche == NULL et 
        node->filsMilieu   == NULL et 
        node->filsDroit    == NULL alors
            (*a_supprimer) = true ;
     sinon 
          (*a_supprimer) = false ;
     fin si     si

Et la fonction principale :

Code :

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

1
2
3
4
5
6
7
 
supprimer_mot( arbre * tree , char * mot )
     bool res ;
     supprimer_noeud( arbre->racine , mot , &res );
     si res == true alors // L'arbre est vide
          free( arbre->racine ); 
     fin si

Au lieu de passer une variable en paramètre tu peux aussi renvoyer un booleen, ça revient au même, c'est une question de goût.

[SpiceGuid]

Ma solution est comparable à celle de PRomu@ld.
La fonction supprime doit renvoyer l'arbre dans lequel tu as supprimé la clé.

Pour le peuse-code je vais essayer d'utiliser ta terminologie, mais en plus:

• j'appèle valCle le premier caractère de la clé courante à retirer
• j'appèle resteCle la chaîne de caractères à droite de valCle
• j'appèle this le noeud en cours de visite
  

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
si valCle < val alors
  filsGauche := (supprime resteCle dans le filsGauche)
  renvoyer this
si valCle > val alors
  filsDroit  := (supprime resteCle dans le filsDroit)
  renvoyer this
sinon on a valCle = val alors
  si filsGauche=NULL et filsDroit=NULL
    si filsMilieu=NULL alors
      renvoyer NULL // et libérer this
    sinon
      filsMilieu := (supprime resteCle dans le filsMilieu)
      si filsMilieu=NULL alors renvoyer NULL // et libérer this
      sinon renvoyer this
    fin si
  sinon
    filsMilieu := (supprime resteCle dans le filsMilieu)
    renvoyer this
  fin si 
fin si

[jurio]

Merci beaucoup pour votre aide les gars!

Je pense avoir mieux compris la maniére dont il faut procéder. J'avais aussi pensé à trouver le mot puis remonter dans l'arbre et supprimer le cas échéant mais je ne voyais comment remonter puisque j'ai pas de pointeurs vers le haut de l'arbre. J'avais pas pensé à la l'utilisation de la récursivité pour récupérer ces informations!!

Juste une question, quand est ce qu'on considère que l'arbre contient tel ou tel mot, faut il qu'il y est obligatoirement un '/0' à la fin du mot recherché dans l'arbre ou bien seul les préfixes suffisent??
Exemple : j'entre le mot : "bonhomme" dans l'arbre donc l'arbre ressemblera a ca :
B
|
O
|
N
|
H
|
O
|
M
|
M
|
E
|
/0

Maintenant, est ce que le mot "bon" est dans l'arbre ou pas ??? Je pense que non mais j'en suis pas sure...auriez vous une idée??

Je vais essayer de coder tout ça et je vous tiens au courant!

Merci encore!!

[PRomu@ld]

Soit tu considère le '\0' dans ton mot et un mot n'existe que s'il contient le '\0'

Dans ton cas, il faudrait :

Code :

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

1
2
3
4
5
6
7
8
  B
  |
  O
  |
  N
 /  \
'\0' H
     |

Pour que bonhomme et bon soient codés. Sinon seul bonhomme est dedans.

[SpiceGuid]

J'avais aussi pensé à trouver le mot puis remonter dans l'arbre et supprimer le cas échéant mais je ne voyais comment remonter puisque j'ai pas de pointeurs vers le haut de l'arbre.

Pour remonter dans l'arbre tu peux utiliser le pointer reversal (inversion des pointeurs).
Le pointer reversal ça consiste à considérer ton cheminement dans l'arbre comme une liste chaînée de noeuds, or tu sais comment retourner une liste chaînée, par conséquent tu sais comment remonter dans l'arbre (faire le cheminement inverse).

Mais c'est bien plus laborieux et moins élégant que la récursion.
Le seul avantage c'est que ça n'utilise pas la pile.