Klasa TrieNode

Lekcja 3 z 14 w kursie Drzewa Trie — struktury danych #8 w Coddy.

Każdy węzeł w drzewie trie to mały obiekt, który przechowuje dwie informacje: dzieci odchodzące od niego (mapę znaków na następne węzły) oraz flagę isEndOfWord, która oznacza, czy ścieżka od korzenia do tego węzła tworzy całe wstawione słowo.

To cała klasa. Nie ma wartości ani kluczy: położenie węzła w drzewie JEST jego znaczeniem. Ścieżka krawędzi oznaczonych c, a, t od korzenia prowadzi do węzła, w którym ustawiamy isEndOfWord = true podczas wstawiania "cat".

Zacznijmy od utworzenia tej klasy TrieNode — klasa Trie z następnej lekcji będzie z niej korzystać.

Wyzwanie

Łatwy

Napisz klasę TrieNode z konstruktorem, który nie przyjmuje żadnych argumentów.

Zainicjalizuj dwa pola:

children ustawione na pustą mapę (lub odpowiednik mapy znaków na węzły w Twoim języku).
isEndOfWord ustawione na false.

Spróbuj swoich sił

#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;
}

Wszystkie lekcje w sekcji Drzewa Trie — struktury danych #8

1Wprowadzenie

Wprowadzenie Czym jest trie?

2Projekt drzewa Trie

Klasa TrieNodeKlasa Trie Wstawianie Wyszukiwanie Zaczyna się od Usuwanie Liczba słów

3Wyzwania praktyczne

Najdłuższy wspólny prefiks Policz słowa z danym prefiksem Autouzupełnianie Najdłuższe słowo w słowniku Dzielenie słowa

Poćwicz samodzielnie: Kompilator C online