Wstawianie
Lekcja 5 z 14 w kursie Drzewa Trie — struktury danych #8 w Coddy.
Aby wstawić słowo do drzewa trie, przechodź od korzenia w dół, po jednym znaku naraz. Dla każdego znaku słowa: jeśli bieżący węzeł nie ma potomka dla tego znaku, utwórz nowy węzeł TrieNode i dołącz go. W obu przypadkach przejdź do tego potomka i kontynuuj od następnego znaku.
Gdy dotrzesz do końca słowa, oznacz węzeł, na którym się zatrzymałeś, za pomocą isEndOfWord = true. Ta flaga pozwala później odróżnić rzeczywiste zapisane słowo od ścieżki, która istnieje jedynie dlatego, że jest prefiksem czegoś innego.
Wstawienie najpierw "cat", a następnie "car" sprawia, że ścieżka c -> a jest współdzielona, a rozgałęzienie pojawia się dopiero przy trzecim znaku. To współdzielenie sprawia, że drzewa trie są tak oszczędne pod względem miejsca w przypadku słowników.
Wyzwanie
ŁatwyDodaj metodę insert do klasy Trie.
Przyjmuje ona ciąg znaków word i zapisuje go w trie:
- Zacznij od
root. Dla każdego znakucwword, jeśli bieżący węzeł nie ma potomka dlac, dodaj tam nowy węzełTrieNode. - Przejdź do tego potomka i kontynuuj.
- Po ostatnim znaku ustaw
isEndOfWordostatniego węzła natrue.
Spróbuj swoich sił
#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"); }
if (strcmp(cmd, "hasChild") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", t.root->children[(unsigned char)arg[0]] != NULL ? "true" : "false"); }
if (strcmp(cmd, "insert") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Trie_insert(&t, arg); }
}
return 0;
}
Wszystkie lekcje w sekcji Drzewa Trie — struktury danych #8
Poćwicz samodzielnie: Kompilator C online