Печать всех слов из префикса по порядку

Question

Я создал программу, которая может принимать пользовательский ввод для создания префиксного дерева. Каждый персонаж - это узел, который связан вместе. У меня есть команда «print», которая будет печатать слова следующим образом, если пользователь ввел этот ввод: cat, car, sat, saw: ca (R, T), sa (T, W).

Я пытаюсь создать две функции, которые вместо этого будут распечатывать слова, данные от пользователя в алфавитном слове. Одна функция PrintAllWords() - это функция, которая будет выполнять большую часть работы, я думаю, что эта функция будет рекурсивной функцией, которая будет печатать в глобальную строку какого-либо рода каждое слово через push_back(), а затем удалять это текущее словоот pull_back () и перейти к следующему. Вторая функция printWordList();позвонил бы printAllWords();и просто распечатать список слов создать.

Я начал с некоторого кода, пытающегося медленно добраться туда, куда я хочу, но в тот момент, когда я использую команду «список» (команда для новых функций), мой код дает мне только родительские узлыC и S как показано ниже: cs.

Как я могу просто получить первые узлы каждого слова, попробовать и получить первое слово в префиксе дерева «cat».

My Header File:

#ifndef __PREFIX_TREE_H
#define __PREFIX_TREE_H

#include <iostream>
using namespace std;

const int ALPHABET_SIZE = 26;

class PrefixTreeNode;

/*
  Prefix tree
  Stores a collection of strings as a tree
 */
class PrefixTree
{

private:
  PrefixTreeNode* root;
public:
  //Constructs an empty prefix tree
  PrefixTree();
  //Copy constructor
  PrefixTree(const PrefixTree&);
  //Copy assignment
   const PrefixTree& operator=(const PrefixTree&);
  //Utility func: checks whether all characters in str are letters
  bool isAllLetters(const string&) const;
  //Returns the root of the prefix tree
  PrefixTreeNode* getRoot() { return root; };
  //Returns the root of the prefix tree
  const PrefixTreeNode* getRoot() const { return root; };
  //Returns whether or not the given word belongs to the prefixtree
  bool contains(const string&) const;
  //Adds the given word to the prefix tree
  void addWord(const string&);
  //Prints all of the words in the prefix tree
  void printWordList() const;
  //Destructor
  ~PrefixTree();
};

/*
  Node of a prefix tree
 */
class PrefixTreeNode
{
  friend PrefixTree;
private:
  char c;
  bool final;
  PrefixTreeNode* link[ALPHABET_SIZE];
public:
  //Constructs a new node
  PrefixTreeNode();
  //Copy constructor
  PrefixTreeNode(const PrefixTreeNode&);
  //Copy assignment
  const PrefixTreeNode& operator=(const PrefixTreeNode&);
  //Returns the character this node contains
  char getChar() const { return c; }
  //Returns whether this node is the end of a word
  bool isFinal() const { return final; }
  //Changes whether this node is the end of a word
  void setFinal(bool b) { final = b; }
  //Returns the node corresponding to the given character
  PrefixTreeNode* getChild(char);
  //Returns the node corresponding to the given character
  const PrefixTreeNode* getChild(char) const;
  //Adds a child corresponding to the given character
  void addChild(char);
  //Removes the child corresponding to the given character
  void deleteChild(char);
  //print all words that end at or below this PrefixTreeNode
  void printAllWords() const;
  //Destructor
  ~PrefixTreeNode();
};

ostream& operator<<(ostream&, const PrefixTree&);
ostream& operator<<(ostream&, const PrefixTreeNode&);
#endif

Функции моего исходного файла:

void PrefixTreeNode::printAllWords() const{

for (char c = 'a'; c < 'z' + 1; c++)
    {
      if (this->getChild(c) == nullptr)
        continue;

        this->getChild(c);
      cout << c;
    }

}

//Calls all words
void PrefixTree::printWordList() const{

    PrefixTreeNode* node = root;
    node->printAllWords();
}

PrefixTreeNode* PrefixTreeNode::getChild(char c)
{
  if (isalpha(c))
    return link[tolower(c)-'a'];
  else
    return nullptr;
}

void PrefixTree::addWord(const string& str)
{
  PrefixTreeNode* node = root;
  for (int i = 0; i < str.size(); i++)
  {
    if (node->getChild(str[i]) == nullptr)
      node->addChild(str[i]);
    node = node->getChild(str[i]);
  }
  node->setFinal(true);
}

Answer 1

Мы используем рекурсию для печати всех сохраненных строк в дереве по порядку. Вызовите функцию из основного, используя printAllWords(root, ""). Если root указывает на nullptr, мы возвращаемся. Если root->final равно true, мы печатаем слово. Затем мы добавляем текущий символ к word, перебираем все его дочерние элементы и вызываем printAllWords для каждого из них.

То же самое произойдет для каждого узла.

void printAllWords(Node* current, std::string word)
{
    if (current == nullptr)
        return;

    if (current->final)
        std::cout << (word+current->c) << std::endl;

    for (int i = 0; i < ALPHABET_SIZE; ++i)
        printAllWords(current->link[i], word + current->c);
}

Править: Хотя я должен признаться, я не уверен, какой смысл использовать c в триоде. Если вы построите дерево таким образом, что если, скажем, 2-й дочерний элемент (b) текущего узла не равен нулю, то это означает, что b является частью следа другого слова через него. Следующий код должен прояснить это:

void printAllWords(Node* root)
{
    string word = "";
    for (int i = 0; i < ALPHABET_SIZE; ++i)
        printAllWords(root->link[i], word + (char)(i + 'a'));
}

void printAllWords(Node* current, std::string word)
{
    if (current == nullptr)
        return;

    if (final)
        std::cout << word << std::endl;

    for (int i = 0; i < ALPHABET_SIZE; ++i)
        printAllWords(current->link[i], word + (char)(i + 'a'));
}