c++nodesprefix-tree

Recursive function gives segmentation fault, how to point a pointer object to it's child?


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

Solution

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