So I have a prefixtree object that has multiple nodes. Each node consists of a character, whether it is a final node, and it's children stored in an object pointer array (up to 26 values). I need to print the words found beneath a given node.
Example below.
a
/ \
b c
\
t
If the function is called on the node with character 'a' it should print ab and act. I plan to do this by adding to a string until reach a node marked final and then removing that letter. I want to implement a recursive function but when setting a node to the child of that node I get a segmentation fault.
void PrefixTreeNode::printAllWords() const
{
PrefixTreeNode* node;
for(char i = 'a'; i < 'a' + ALPHABET_SIZE; i++)
{
if(getChild(i) != nullptr)
{
if(!isFinal())
{
nodeList.push_back(i);
cout << "added: " << i << endl;
node = node->getChild(i); //this line results to segmentation fault
node->printAllWords(); //How would I call the function on the node's child?
}
else if(isFinal())
{
nodeList.push_back(i);
cout << nodeList;
nodeList.pop_back();
return;
}
}
}
}
Get child function:
PrefixTreeNode* PrefixTreeNode::getChild(char c)
{
if (isalpha(c))
return link[tolower(c)-'a'];
else
return nullptr;
}
const PrefixTreeNode* PrefixTreeNode::getChild(char c) const
{
if (isalpha(c))
return link[tolower(c)-'a'];
else
return nullptr;
}
Node Object:
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);
//TODO: print all words that end at or below this PrefixTreeNode
void printAllWords() const;
//Destructor
~PrefixTreeNode();
};
If I just tell you why the line is caused of segment fault, I can say that you may initialize the variable node, above the line.
I couldn't know whole code, but I recommend to change it to like this.
void PrefixTreeNode::printAllWords() const
{
for(char i = 'a'; i < 'a' + ALPHABET_SIZE; i++)
{
PrefixTreeNode* node = getChild(i);
//if(getChild(i) != nullptr)
if(node != nullptr)
{
nodeList.push_back(i);//this line will be run, ALWAYS whatever the return of isFinal, so I moved it to here.
if(!isFinal())
{
//nodeList.push_back(i); //moved to the front of 'if'
cout << "added: " << i << endl;
//just remove it
//node = node->getChild(i); //this line results to segmentation fault
node->printAllWords(); //How would I call the function on the node's child?
}
//else if(isFinal()) //duplicated
else
{
//nodeList.push_back(i); //moved to the front of 'if'
cout << nodeList; //I don't know the type of nodeList, but you may take care of it.
nodeList.pop_back();
return;
}
}
}
}