Printing all the words from a prefixtree in order

Question

I've set up a program that can take in user input to create a prefixtree. Each character is a node which are linked together. I have a "print" command that will print the words out as the following if the user gave this input: cat, car, sat, saw: ca(R,T),sa(T,W).

I'm trying to create two functions that will instead print out the words given from the user in alphabetical word. One function PrintAllWords() is the function that will be doing most of the work, I'm thinking of having this function be a recursive function that would print to a global string of some sort each word through push_back() then delete that current word from pull_back() and move onto the next. The second function printWordList(); would call printAllWords(); and just print out the list of words create.

I've start with some code trying to slowly get to where I want, but at the moment when I use the command "list" (the command for the new functions) my code only gives me the parent nodes C and S as the following: cs.

How can I just get the first nodes of each word, try and get the first word in the prefixtree being "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

My Source File functions:

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

We use recursion to print all the stored strings in the tree in order. Call the function from main using printAllWords(root, ""). If root points to nullptr, we return. If root->final is true, we print the word. Then we append the current character to word and loop through all it's children and call printAllWords for each of them.

The same will happen for every node.

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

Edit: Although I must confess I'm not sure what's the use of c in the treenode. If you construct the trie such that if let's say the 2nd child (b) of the current node is not null, then that means that b is part of a trail of another word(s) through it. The following code should make it clear:

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