Afficher un arbre lexicographique

Question

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

MaxSoldier · Answer

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

MasterShadows · Answer

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

Lyle56 · Answer

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.

MasterShadows · Answer

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

sinzo · Answer

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

Afficher un arbre lexicographique

5 réponses

Votre réponse

Discussions similaires