Question

I am getting a seg fault with my huffman tree. I'm not sure if it's my deconstructors but also getting some memory leaks. Can some one help me find my seg fault? It's in c++, thanks!

//#ifndef HUFFMAN_HPP
//#define HUFFMAN_HPP

#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include <string>
#include <iostream>
using namespace std;

class Node {
public:
    // constructor with left and right NULL nodes
    Node(char charTemp, int c) {
      ch = charTemp;
      count = c;
      left = NULL;
      right = NULL;
    };

// constuctor used while building the tree
Node(char charTemp, int c, Node *n1, Node *n2) {
    ch = charTemp;
    count = c;
    left = n1;
    right = n2;
};

/* ~Node() {
    delete left;
    delete right;
}*/

~Node() {
   if(left != NULL)
       delete left;
   if(right != NULL)
       delete right;
}

int count; // counting the frequency of the character in the string
char ch;
Node *left;
Node *right;
};

struct Comp { // compare used while building the minheap
bool operator()(const Node *a, const Node *b) {
    return a->count > b->count;
}
};
// our class
class Huffman {

private:
    std::priority_queue,Comp> pq; // using standard priority queue
std::vector a;
std::vector nodeCounter;
Node *root;

void incrementCount(char inc) {
    // internal function to calculate the frequency of the character in the string
    for (int i = 0; i < nodeCounter.size(); i++) {
      if (nodeCounter.at(i) -> ch == inc) {
        nodeCounter.at(i) -> count++; // incrementing the frequency of the character
        return;
      }
    }
}

public:
    // default constructor
    Huffman() {

    }
    // deconstructor
    ~Huffman() {
    // delete root;
      for (int i = 0; i < nodeCounter.size(); i++) {
        delete nodeCounter.at(i);
      }
      //delete root;
    }
    // to build the tree*/
void build_tree(std::string str) {

      for (int i = 0; i < str.length(); i++) {
        std::vector::iterator it = find(a.begin(), a.end(), str[i]); // finding the character in our previous built vector

        if (it == a.end()) // adding to the vector, if it was not added previously
        {
          a.push_back(str[i]);
          Node *n = new Node(str[i], 1);
          nodeCounter.push_back(n);

        } else { // incrementing the character frequency if it has already been added

          incrementCount(str[i]);
        }
      }

      for (int i = 0; i < nodeCounter.size(); i++) {
        pq.push(nodeCounter.at(i)); // adding the nodes to the priority queue which will help us to build the tree
      }

      while (pq.size() != 1) {

        Node *n1 = pq.top();
        pq.pop();
        Node *n2 = pq.top();
        pq.pop();

        Node *root = new Node('*', n1 -> count + n2 -> count, n1, n2);

        pq.push(root); // pushing the new node by combining the least frequent characters

      }

      root = pq.top(); // defining the root of the tree

    }
    // encode function
std::string encode(std::string code) {
      std::string ret = "";
      for (int i = 0; i < code.length(); i++) {
        ret = ret + encodeUtil(code[i], "", root); // finding the code of each character and combining them
      }

      return ret;
    }
    // recurisvely called in our encode function
std::string encodeUtil(char ch, std::string code, Node *m) {

    if (m == NULL) {
      return " ";
    }

    if (ch == m -> ch) {
      return code;
    }

    // calling the utility function for the left node
    std::string ret1 = encodeUtil(ch, code + "0", m -> left);

    if (ret1.compare(" ") != 0)
      return ret1;
       // calling function for right node
    std::string ret2 = encodeUtil(ch, code + "1", m -> right);
    if (ret2.compare(" ") != 0)
      return ret2;

    return " ";
}

std::string serialize() {
    // calling the serialize util function to make use of the root in a recursive way
    return serializeUtil(root, "");
}

// serializing util function
std::string serializeUtil(Node *root, std::string ret) {

    if (root == NULL) {
      return ret + "/"; // if the node is null then serializing it as '/''
    }

    ret = ret + root -> ch; // adding the character to the returning string
// ser left
    ret = serializeUtil(root -> left, ret);
// ser right
    ret = serializeUtil(root -> right, ret);

    return ret; // return string
}

};

int main() {
std::string input;

while (true) {

    // capturing the input from the user
    std::cout << "Input string: ";
    //std::cin >> input;
    std::getline (std::cin, input);
    if (input.compare("q") == 0)
      return 0;

    Huffman *h = new Huffman();

    // building the tree
    h->build_tree(input);

    std::cout << std::endl;
    // printing the encode of the string
    std::cout << h->encode(input) << std::endl;

    // serializing the tree
    std::cout << h->serialize() << std::endl;

    delete h;
}
}

//#endif

Answer 1

Segmentation Fault is caused by trying to access memory that doesn't exist.

We need to double check all your pointers and make sure you are trying to access the information that you intended (address/value).

This might be the issue:

private:
    std::priority_queue,Comp> pq; // using standard priority queue

  std::priority_queue<HuffmanNode, std::vector<HuffmanNode>, Comp > pq;

You can also open the program in the debugger step through and find the source of the SEGFAULT. and the question and post it again.