Класс TrieNode
Урок 3 из 14 курса Префиксные деревья (Trie) — Серия «Структуры данных» №8 на Coddy.
Каждый узел в префиксном дереве (trie) — это один небольшой объект, который содержит две части информации: children (дочерние узлы), отходящие от него (отображение символа на следующий узел), и флаг isEndOfWord, который отмечает, составляет ли путь от корня к этому узлу полное вставленное слово.
Это и есть весь класс. Никаких значений, никаких ключей: положение узла в дереве И ЕСТЬ его значение. Путь из ребер, помеченных c, a, t, от корня ведет к узлу, где мы устанавливаем isEndOfWord = true при вставке "cat".
Давайте начнем с создания этого класса TrieNode — класс Trie в следующем уроке будет его использовать.
Задание
ЛегкоНапишите класс TrieNode с конструктором, который не принимает аргументов.
Инициализируйте два поля:
children, установленное в пустой словарь (или эквивалент вашего языка для сопоставления символов с узлами).isEndOfWord, установленное в false.
Попробуйте сами
#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;
}