Discussion :

[ColonelHati]

Bonjour a tous,

je souhaiterai construire un arbre lexicographique dont chaque noeud contient non pas une lettre mais une ou plusieurs lettres (comme ici), mais je me casse la tête sur l'algo nécessaire...
Quelqu'un pourrait-il m'aider, je n'ai pas trouvé de lien satisfaisant...

Merci d'avance!

[PRomu@ld]

As tu déjà fait quelque chose ?

Perso, je ferai ainsi :

-> Lorsque tu veux ajouter un mot, tu commences à la racine (jusque là, tout est normal ),
-> Si le noeud courrant est vide, alors tu insère le mot.
-> Si le noeud n'est pas vide mais que la première lettre ne correspond pas, il faut insérer au dessous du noeud.
-> Si la première lettre correspond, alors tu regarde la lettre qui ne correspond plus (en gros, tu élimines les lettres dans le noeud pour savoir où tu doit découper).
-> Si lors de tes éliminations de lettres, tu as pu passer toutes les lettres du noeud alors tu passes au noeud de droite.
-> Si tu es tombé sur une lettre qui ne correspond plus, il faut alors que tu découpes. Ici, tu commences par découper le noeud en deux noeuds (un noeud avec les lettres qui correspondent et l'autre avec le reste du mot). Une fois que tu as découpé tu insères le reste de ton mot dans le noeud du dessous.

Le tout est donc très naturellement récursif. A quelques détails près, la méthode doit être là.

[ColonelHati]

Non je n'avais encore rien de concret.

Je vais essayer de faire l'algo, mais moi et la récursivité, c'est pas le grand amour...

Si quelqu'un a d'autres conseils je suis preneur!

Merci.

[PRomu@ld]

mais moi et la récursivité, c'est pas le grand amour...

En fait, les algos sur les arbres et surtout ici (ou en fait tu as une forêt) sont naturellement récursifs.

Bien sur, il peut (toujours) exister un algorithme itératif mais il sera généralement plus compliqué.