Classe TrieNode
Leçon 3 sur 14 du cours Tries - Série Structures de données n°8 de Coddy.
Chaque nœud d'un trie est un petit objet qui contient deux informations : les children qui en dépendent (une map d'un caractère vers le nœud suivant) et un drapeau (flag) isEndOfWord qui indique si le chemin depuis la racine jusqu'à ce nœud forme un mot complet inséré.
C'est l'intégralité de la classe. Pas de valeurs, pas de clés : la position d'un nœud dans l'arbre EST sa signification. Un chemin d'arêtes étiquetées c, a, t depuis la racine atteint le nœud où nous définissons isEndOfWord = true lorsque nous insérons "cat".
Commençons par construire cette classe TrieNode - la classe Trie de la prochaine leçon l'utilisera.
Défi
FacileÉcrivez une classe TrieNode avec un constructeur qui ne prend aucun paramètre d'entrée.
Initialisez deux champs :
childrendéfini sur une map vide (ou l'équivalent de votre langage pour une map de caractère à nœud).isEndOfWorddéfini sur false.
Essayez vous-même
#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;
}