Afficher un arbre lexicographique

Signaler
Messages postés
268
Date d'inscription
lundi 1 mars 2004
Statut
Membre
Dernière intervention
19 avril 2012
-
sinzo
Messages postés
91
Date d'inscription
lundi 9 juin 2008
Statut
Membre
Dernière intervention
23 septembre 2011
-
Bonjour à tous,
alors j'ai un soucis, je dois créer un arbre lexicographique avec les opérations suivantes : insertion, teste d'appartenance, affichage de l'arbre, etc...

Donc pour tout ce qui est insertion, teste d'appartenance, ça va, le plus gros problème est l'affichage de l'arbre; effectivement l'arbre se représente ainsi :

                                  a
                                 /  \
                                .    b
                                     / \
                                    a   u
                                   / \    /  
                                  l   s   s  
                                 /   /    / 
                               l     e   .
                              /      /
                             e     .
                            /
                           .

Maintenant pour l'affichage, on doit avoir les résultats suivants :

a
balle
base
bus

Comment puis-je afficher les mots voulus en partant de cette arbre ? J'ai bien essayé les parcours infixe, suffixe et préfixe mais non j'obtiens pas le résultat voulu.

Le dico est défini ainsi ;

class Dictionnaire
{
      char val;
      Dictionnaire left;
      Dictionnaire right;

      // ....

      void affiche(Dictionnaire t)
      {
            /// ??????????????????
      }
}

Comment puis-je donc faire ?

En vous remerciant....
A voir également:

5 réponses

Messages postés
289
Date d'inscription
dimanche 10 août 2003
Statut
Membre
Dernière intervention
28 février 2009
2
Yop !
Je pense que ton arbre est mal formé à la base. En effet, il te manque un condition : Que le mot existe !
En faisant un parcours préfix récursif, on obtient les mots :
- a.
- aballe.
- abase.
- abus.

En effet, ta root nood doit être une lettre commune à tous les mots (Comme le b qui est commun à balle, bus et base).
Pour résoudre le problème, il suffit que ta root node ne contienne pas de lettre mais simplement un node vierge liant les lettre de début de mot.

Bonne chance !

-=Ar$£nik=-
Messages postés
268
Date d'inscription
lundi 1 mars 2004
Statut
Membre
Dernière intervention
19 avril 2012
10
Salut,
ton idée est interessante , mais dans cet exo, il s'agit d'un arbre binaire dont les noeuds qui partent à gauche sont des lettres du mot et les noeuds de droite permettent de former un nouveau mot.

tu peux aller ici pour avoir plus d'info sur le truc en question :

https://cid-ac30d181a69afcad.skydrive.live.com/browse.aspx/AGAP%20-%20TP2%20-%20Arbre%20lexicographique

En ce qui concerne l'idée d'avoir un noeud vierge faisant le lien avec les autres noeuds, je suppose que tu voulais parler d'un arbre n-aire (enfin 26 dans notre cas), j'y ai pensé, ça me semble plus simple pour le pattern matching et l'affichage, mais allons savoir pourquoi le prof en question impose l'arbre binaire.

Je suppose que l'arbre 26-aire était certainement ce qu'il y'avait de mieux à faire pour l'exo (pour un peu on aurait le début d'un jeu de type scrabble) mais non interdit.

En te remerciant
Messages postés
240
Date d'inscription
jeudi 1 mai 2008
Statut
Membre
Dernière intervention
19 juillet 2012
2
D'après se que tu dit, il y as un soucis avec ton arbre quand même ..

il s'agit d'un arbre binaire dont les noeuds qui partent à gauche sont
des lettres du mot et les noeuds de droite permettent de former un
nouveau mot.

Dans ce cas,  la chaine US n'est pas relié à ton B vue que le U est censé être la première lettre d'un nouveau mot.
Messages postés
268
Date d'inscription
lundi 1 mars 2004
Statut
Membre
Dernière intervention
19 avril 2012
10
J'accepte le fait qu'il y'ait un soucis dans l'arbre, ça ne me dérange pas. Cependant, il se peut aussi que je n'ai pas saisi exactement comment fonctionne cet arbre lexicographique binaire (plus d'infos

https://cid-ac30d181a69afcad.skydrive.live.com/browse.aspx/AGAP%20-%20TP2%20-%20Arbre%20lexicographique 
)

Il faut bien saisir que je ne cherche pas une réponse toute faite mais moultes explications (oui parce que c'est une habitude là où je suis en étude, c'est que l'on fait des trucs quasimment sans cours) et là ben d'après ce que j'ai pu trouver sur les arbres lexicographiques, ils étaient fait en arbre n-aires et non binaires.

En te remerciant...
Messages postés
91
Date d'inscription
lundi 9 juin 2008
Statut
Membre
Dernière intervention
23 septembre 2011

salut mastershadows , j'ai exactement  le mm probleme que toi squf qu'il s'agit pour moi d'un arbre n aire.. Si seulement tu pouvais m'envoyer ce que tu a trouvé sur les arbres n aires j'en serais tres reconnaissant .. voivi mon adresse snake_solid007@hotmail.com.. svp je dois le presenter apres demain ..merci d'avance