question de la mise en œuvre de l'arbre préfixe de base

Question

Je l'ai mis en place un arbre de préfixe de base ou « Trie ». La structure arborescente se compose de nœuds comme ceci:

// pseudo-code
struct node {
    char c;
    collection<node> childnodes;
};

Dis-je ajouter les mots suivants à mon Trie: « Apple », « Arche » et « chat ». Maintenant, quand je Recherch des préfixes comme « Ap » et « Ca » mon « la bool containsPrefix (préfixe de chaîne) » Trie méthode retourne correctement vrai.

Maintenant, je suis mise en œuvre de la méthode « bool containsWholeWord (mot de chaîne) » qui retourne vrai pour « chat » et « Arche », mais faux pour « App » (dans l'exemple ci-dessus).

Est-il courant pour les nœuds d'un Trie d'avoir une sorte de « endOfWord » drapeau? Cela aidera à déterminer si la chaîne étant en place avait l'air était en fait un mot entier est entré dans la structure arborescente et non juste un préfixe.

Vive!

Answer 1

Si vous devez stocker à la fois « App » et « Apple », mais pas « Appl », alors oui, vous avez besoin de quelque chose comme un drapeau endOfWord.

Sinon, vous pouvez l'intégrer dans votre conception par (parfois) ayant deux noeuds avec le même caractère. Donc, « Ap » doit childNodes: Le nœud feuille « p » et un noeud interne « p » avec un enfant « l »

.

Answer 2

La fin de la clé est généralement indiquée par un nœud feuille. Soit:

• les nœuds enfants sont vides; ou
• vous avez une branche, avec un préfixe de la clé, et certains nœuds enfants.

Votre conception n'a pas une feuille / noeud vide. Essayez indiquant par exemple avec une valeur nulle.