c++ - 按顺序打印前缀树中的所有单词

我已经建立了一个程序，可以接受用户输入来创建前缀树。每个字符都是一个链接在一起的节点。我有一个“打印”命令，如果用户输入以下内容，则会将单词打印如下:cat，car，sat，saw:
ca(R，T)，sa(T，W)。

我正在尝试创建两个函数，以代替以字母顺序打印出用户给出的单词。一个函数PrintAllWords()是将完成大部分工作的函数，我在考虑将此函数作为递归函数，该函数将通过push_back()打印到某种形式的全局字符串，然后从pull_back()中删除当前单词并移至下一个。第二个函数printWordList();会叫printAllWords();并打印出create单词列表。

我从一些代码开始尝试慢慢地到达我想要的位置，但是当我使用命令“list”(新功能的命令)的时候，我的代码只给了我父节点C和S，如下所示:CS

我如何才能获得每个单词的第一个节点，尝试使前缀树中的第一个单词为“cat”。

我的头文件:

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

最佳答案

我们使用递归顺序打印树中所有存储的字符串。使用printAllWords(root, "")从main调用函数。如果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);
}

编辑:虽然我必须承认我不确定在treenode中c的用途。如果构造特里树，使得如果当前节点的第二个子节点(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'));
}

关于c++ - 按顺序打印前缀树中的所有单词，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/58505991/