Discussion :

[youkisall]

Bonjour,
Je veux de l'aide s'ilvous plait , je vais écrire un algorimthe qui prent en parametre un pointeur “arbre” sur la racine de l’arbre, un mot “mot” et la taille n du mot, qui renvoie vrai si le mot est l’´etiquette d’un chemin de l’arbre, et faux sinon.
l'arbre est un abre binaire de recherche qui a des lettres de l'alphabet, chaque lettre est présente une seule fois et la valeur des lettre est croissante c'est a dire A<B<C<D......
le mot est la concaténation de l'étique (de la racine vers la feuille)

Je sais que je dois au moins vous donner le debut de ce que j'ai fait, mais suis vraiment bloguer

J'ai juste fait ce qui suis et je pense que je dois parcourir tout l'abre et ensuite comparé apres avoir concaténé les étiques qui se font (de la racine vers les feuilles)

Donc voici ce que j'ai fait pr le moment :

Algo verifier (poiteur<abre T>, mot, n)

reponse = faux;
// je considere qu'il faut parcourir l'abre en preordre (partant tjrs de la racine)
1. Si (racine existe)
2. traiter(racine) ;
3. preOrdre(racine->filsGauche);
4. preOrdre(racine->filsDroit);


voila je suis bloqué, comment aprés avoir parcouru l'arbre récupérer la concatenation des noeuds de chaque chemin (dela racine aux feuilles) pour ensuite le comparer au mot mis en paramétre pour dire si oui ou non ce mot (en parametre) existe dans l'abre?
Merci bcp de votre aide

[ToTo13]

bonjour,

si j'ai bien compris, tu as un arbre, donc chaque noeud a 26 feuilles.
Donc il te suffit de décomposer ton mot en une suite de caractère et d'avancer lettre par lettre dans l'arbre.
Si tu arrives à la fin du mot, c'est qu'il est dans l'arbre.
Si une feuille est manquante, c'est que le mot n'est pas dans l'arbre.

PS : si c'est un exercice que l'on te donne ok. Si c'est toi qui veut faire un dictionnaire et stocker des mots, c'est la mauvaise méthode et il faut utiliser une table de hashage...

[Hephaistos007]

Je ne comprends pas l'intérêt de cet exercice, mais voici 2 néanmoins remarques :

1. L'intérêt de l'arbre binaire ordonné (ici muni d'une relation d'ordre lexicographique) est de permettre une exploration dichotomique, et non de parcourir tout l'arbre comme tu le dis.
2. Suivant l'ordre dans lequel tu vas insérer tes 26 lettres de l'alphabet, tu vas obtenir des arbres différents (par exemple, tu peux avoir 26 racines différentes).
3. L'idée de l'algorithme est de comparer le caractère courant du mot à tester avec la racine courante de l'arbre, et de relancer récursivement sur le fils droit ou gauche selon l'ordre lexicographique du prochain caractère. Si le dernier caractère du mot peut être atteint ainsi, alors c'est gagné. PS : Inspires-toi de l'algorithme de recherche dans un arbre binaire ordonné.

[Jedai]

PS : si c'est un exercice que l'on te donne ok. Si c'est toi qui veut faire un dictionnaire et stocker des mots, c'est la mauvaise méthode et il faut utiliser une table de hashage...

Pourquoi ? Les tables de hashage n'ont rien de magique et les trie (arbres à lettres) ont plusieurs avantages pour un dictionnaire : d'une part ils permettent une énumération dans l'ordre en O(n), d'autre part on peut trouver tous les mots commençant par un même préfixe...
En terme de complexité, les tables de hashage et les trie sont comparables pour la plupart des opérations, les seuls avantages des hash sur les trie sont généralement l'occupation mémoire (quoique les trie puissent être compressés en utilisant des structures plus avancées comme les patricia trie) et la vitesse dans les meilleures implémentations des deux structures.

Par ailleurs les trie supportent plus facilement une utilisation de type persistante, c'est-à-dire que conserver plusieurs versions d'un même trie n'est pas aussi couteux que de conserver plusieurs versions d'un hash, les trie se prêtent donc mieux à la programmation fonctionnelle.

--
Jedaï