TrieNode-Klasse
Lektion 3 von 14 im Kurs Tries - Datenstrukturen-Serie #8 von Coddy.
Jeder Knoten in einem Trie ist ein kleines Objekt, das zwei Informationen enthält: die davon abhängigen children (eine Map von einem Zeichen zum nächsten Knoten) und ein Flag isEndOfWord, das markiert, ob der Pfad von der Wurzel zu diesem Knoten ein vollständiges eingefügtes Wort bildet.
Das ist die gesamte Klasse. Keine Werte, keine Schlüssel: Die Position eines Knotens im Baum IST seine Bedeutung. Ein Pfad von Kanten, die mit c, a, t beschriftet sind, erreicht von der Wurzel aus den Knoten, an dem wir isEndOfWord = true setzen, wenn wir "cat" einfügen.
Beginnen wir mit dem Erstellen dieser TrieNode-Klasse – die Trie-Klasse in der nächsten Lektion wird sie verwenden.
Aufgabe
EinfachSchreiben Sie eine Klasse TrieNode mit einem Konstruktor, der keine Eingabe erwartet.
Initialisieren Sie zwei Felder:
childrengesetzt auf eine leere Map (oder das Äquivalent Ihrer Sprache für eine Zeichen-zu-Knoten-Map).isEndOfWordgesetzt auf false.
Probier es selbst
#include <stdio.h>
#include "trienode.h"
int main() {
TrieNode* n = TrieNode_new();
printf("%s %s\n",
TrieNode_childrenCount(n) == 0 ? "true" : "false",
n->isEndOfWord ? "true" : "false");
return 0;
}