Classe Trie
Leçon 4 sur 14 du cours Tries - Série Structures de données n°8 de Coddy.
La classe Trie elle-même est très légère : elle possède un seul champ, root, qui est un TrieNode. Chaque insertion, recherche et consultation commence à partir de cette racine et parcourt l'arborescence un caractère à la fois.
Le constructeur crée un nouveau TrieNode pour la racine. Cette racine n'a pas encore d'enfants et n'est pas marquée comme la fin d'un mot, donc le trie commence vide. Les méthodes que nous ajouterons dans les prochaines leçons feront croître des enfants à partir d'elle.
Défi
FacileÉcrivez une classe Trie avec un constructor qui ne prend aucun paramètre d'entrée.
Initialisez un champ unique root comme un nouveau TrieNode (en utilisant la classe que vous avez écrite dans la leçon précédente).
Essayez vous-même
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "trie.h"
int main() {
Trie t;
Trie_init(&t);
char line[1024];
while (fgets(line, sizeof(line), stdin)) {
line[strcspn(line, "\r\n")] = '\0';
char* cmd = strtok(line, " \t");
if (!cmd) continue;
if (strcmp(cmd, "rootIsEmpty") == 0) { printf("%s\n", TrieNode_childrenCount(t.root) == 0 ? "true" : "false"); }
}
return 0;
}