Arbre Ternaire - Suppression

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:

---

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

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

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

---

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.

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:

---

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

---

Merci beaucoup pour votre aide les gars! :D

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!!

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:

---

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.

Citation:

---

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.

Ok PRomu@ld, concernant si un mot est oui ou non dans l'arbre, cela dépend des conventions fixées. Tout à fait, dans mon cas, un mot est dans l'arbre si la lettre /0 l'est aussi.

Je suis d'accord avec toi SpiceGuid, les appels récursives blindent la pile mais bon, C'est une bonne occasion pour moi de s'entrainer sur la récursivité que je ne maîtrise pas!!! :aie:

Merci pour votre aide !