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

Question

J'ai implémenté un arbre de préfixe de base ou "trie". Le trie consiste en des noeuds comme celui-ci :

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

Supposons que j'ajoute les mots suivants à mon tableau : "Apple", "Ark" et "Cat". Maintenant, lorsque je cherche des préfixes comme "Ap" et "Ca", la méthode "bool containsPrefix(string prefix)" de ma trie renvoie correctement true.

J'implémente maintenant la méthode "bool containsWholeWord(string word)" qui renverra true pour "Cat" et "Ark" mais false pour "App" (dans l'exemple ci-dessus).

Est-il courant que les nœuds d'un tableau aient une sorte d'indicateur "endOfWord" ? Cela aiderait à déterminer si la chaîne de caractères recherchée était en fait un mot entier entré dans le tableau et pas seulement un préfixe.

A la vôtre !

Answer 1

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 quelques noeuds enfants.

Votre conception n'a pas de nœud feuille/vide. Essayez de l'indiquer avec un null par exemple.

Answer 2

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

Vous pouvez aussi l'intégrer dans votre conception en ayant (parfois) deux nœuds avec le même caractère. Ainsi, "Ap" a deux noeuds enfants : Le noeud feuille "p" et un noeud interne "p" avec un enfant "l".