Как напечатать все слова в Trie?

Question

Как напечатать все слова в Trie?

Я пытаюсь создать Trie Реализация на C ++. Я не могу понять, как напечатать все слова, хранящиеся в Trie,

Вот как я реализовал TrieNode,

struct TrieNode{
bool isWord;
int data; //Number of times Word Occured
TrieNode *Child[ALPHABET_SIZE]; //defined as 26
};

Я знаю, что могу хранить pointer в родительский узел, поиск в глубину для всех узлов, где isWord==True и рекурсивно печатать каждое слово из этих узлов.

Но мне интересно, есть ли способ распечатать каждое слово в Trie с моей реализацией TrieNode,

Спасибо за любую помощь.

5

c++data-structures trie

Решение

Другие решения

Вам не нужен ваш родительский узел, ваш код легко приспосабливается к обходу через рекурсию. Псевдо-код:

void traverse(string prefix, TrieNode const& n) {
prefix += static_cast<char>(n.data);

if (n.isWord)
print(prefix);

for (auto const next : n.Child)
if (next)
traverse(prefix, *next);
}

Это более или менее действительный C ++. Просто определите print соответственно.

РЕДАКТИРОВАТЬ В ответ на комментарий Якка и ваше разъяснение, вот версия, которая не предполагает, что data содержит текущий символ (плохой промах с моей стороны!):

void traverse(string const& prefix, TrieNode const& n) {
if (n.isWord)
print(prefix);

for (std::size_t i = 0; i < ALPHABET_SIZE; ++i)
if (n.child[i])
traverse(prefix + ('a' + i), *n.child[i]);
}

Я оставлю более эффективную реализацию ответа Якка.

5

void traversePrint(TrieNode* sr,char* out,int index)
{
if(sr!=NULL)
{
for(int i=0;i<SIZE;i++)
{
if(sr->child[i]!=NULL)
{
out[index] = 'a'+i;
traversePrint(sr->child[i],out,index+1);
}
}
if(sr->isEnd)
{
out[index]='\0';
cout << out << endl;
}
}
}

// вызов

char out[MAX_WORD_SIZE];
traversePrint(root,out,0);

0

Я не думаю, что здесь нужен isword. Наличие указателя на детей будет достаточно для обхода дерева для доступных слов в дереве.
чтобы найти слово, начните с корня и найдите текущий символ в слове во время любого рекурсивного шага.

struct trie {
trie *children[ALPHABET_SIZE];
};void traversal(trie *&t, string &str) {
bool is_seen = false;
for(int i = 0; i < ALPHABET_SIZE; i++) {
if(t->children[i]) {
if(!is_seen) {
is_seen = true;
}
str.push_back(t[i]);
traversal(t->children[i], str);
str.pop_back();
}
}
if(!is_seen) {
cout << str << "\n";
}

}

-1

Источник

Accepted Answer

Вот разумно эффективная версия Конрада Рудольфа, не предполагая, что данные — это символ. Я также удалил O (n ^ 2) общей памяти, выделенной в версии Конрада, за счет использования std::string&, Идея состоит в том, чтобы передать префикс и изменять его при каждой рекурсии, вставляя символы в конец и после этого выдавливая его, что в итоге оказывается немного более эффективным, чем безумное копирование.

void traverse(std::string& prefix, TrieNode const& node) {
if (node.isWord)
print(prefix);

for (char index = 0; index < ALPHABET_SIZE; ++index) {
char next = 'a'+index;
TrieNode const* pChild = node.Child[index];
if (pChild) {
prefix.push_back(next);
traverse(prefix, *pChild);
prefix.pop_back();
}
}
}

10