Domanda di implementazione dell'albero di base

Question

Ho implementato un albero di prefisso di base o "Trie". Il trie è costituito da nodi come questo:

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

Di 'che aggiungo le seguenti parole al mio Trie: "Apple", "Ark" e "Cat". Ora, quando cerco prefissi come "AP" e "CA" il metodo "bool contiene il prefisso (stringa prefisso)" restituirà correttamente vero.

Ora sto implementando il metodo "Bool contenentewhord (Word String)" che restituirà vero per "Cat" e "Ark" ma False per "App" (nell'esempio sopra).

È comune per i nodi in un trie avere una sorta di flag "endofword"? Ciò aiuterebbe a determinare se la stringa che era in cerca fosse in realtà un'intera parola inserita nel trie e non solo un prefisso.

Saluti!

Answer 1

Se hai bisogno di archiviare sia "app" che "Apple", ma non "Appl", allora sì, hai bisogno di qualcosa di simile a un endOfWord bandiera.

In alternativa, potresti adattarlo al tuo design (a volte) con due nodi con lo stesso carattere. Quindi "AP" deve a Childnodes: il nodo foglia "P" e un nodo interno "p" con un bambino "l".

Answer 2

L'estremità della chiave è generalmente indicata tramite un nodo foglia. O:

• I nodi del bambino sono vuoti; o
• Hai un ramo, con un prefisso della chiave e alcuni nodi per bambini.

Il tuo design non ha un nodo foglia/vuoto. Prova a indicarlo con ad esempio un null.