Grundlegende Frage des Präfixbaums -Implementierung

Question

Ich habe einen grundlegenden Präfixbaum oder "Trie" implementiert. Der Trie besteht aus solchen Knoten:

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

Sagen Sie, ich füge meinem Trie die folgenden Wörter hinzu: "Apple", "Ark" und "Cat". Wenn ich nun Präfixe wie "AP" und "CA" anschaue, wird die Methode vonPrefix (String Prefix) "My Tries" korrekt true zurückgegeben.

Jetzt implementiere ich die Methode "bool contswhaleword (Stringwort)", die für "Cat" und "Ark", aber für "App" (im obigen Beispiel) zutreffend zurückgibt.

Ist es für Knoten in einem Trie üblich, eine Art "EndofWord" -Flag zu haben? Dies würde helfen, festzustellen, ob die Suchstrahlung tatsächlich ein ganzes Wort war, das in den Trie eingegeben wurde, und nicht nur ein Präfix.

Prost!

Answer 1

Wenn Sie sowohl "App" als auch "Apple" speichern müssen, aber nicht "Appl", dann brauchen Sie so etwas wie eine endOfWord Flagge.

Alternativ können Sie es in Ihr Design einfügen, indem Sie (manchmal) zwei Knoten mit demselben Charakter haben. Also muss "AP" Childnodes: den Blattknoten "P" und einen internen Knoten "P" mit einem Kind "L".

Answer 2

Das Ende des Schlüssels wird normalerweise über einen Blattknoten angezeigt. Entweder:

• Die Kinderknoten sind leer; oder
• Sie haben einen Zweig mit einem Präfix des Schlüssels und einigen Kinderknoten.

Ihr Design hat kein Blatt/leerer Knoten. Versuchen Sie, es mit einem NULL anzuzeigen.