I am getting a seg fault with my huffman tree. I\'m not sure if it\'s my deconst
ID: 3836275 • Letter: I
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
#include
#include
#include
#include
#include
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
Explanation / Answer
#include
#include
#include
#include
#include
#include
class Node {
public:
Node(char charTemp, int c) {
ch = charTemp;
count = c;
left = NULL;
right = NULL;
};
Node(char charTemp, int c, Node *n1, Node *n2)
{
ch = charTemp;
count = c;
left = n1;
right = n2;
};
~Node() {
if(left != NULL)
delete left;
if(right != NULL)
delete right;
}
int count;
char ch;
Node *left;
Node *right;
};
struct Comp
{
bool operator()(const Node *a, const Node *b)
{
return a->count > b->count;
}
};
class Huffman {
private:
std::priority_queue,Comp> pq;
std::vector a;
std::vector nodeCounter;
Node *root;
void incrementCount(char inc)
{
for (int i = 0; i < nodeCounter.size(); i++)
{
if (nodeCounter.at(i) -> ch == inc)
{
nodeCounter.at(i) -> count++;
return;
}
}
}
public:
Huffman() {
}
~Huffman()
{
for (int i = 0; i < nodeCounter.size(); i++) {
delete nodeCounter.at(i);
}
}
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]); vector
if (it == a.end())
{
a.push_back(str[i]);
Node *n = new Node(str[i], 1);
nodeCounter.push_back(n);
} else
{
incrementCount(str[i]);
}
}
for (int i = 0; i < nodeCounter.size(); i++) {
pq.push(nodeCounter.at(i));
}
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); }
root = pq.top(); }
std::string encode(std::string code) {
std::string ret = "";
for (int i = 0; i < code.length(); i++) {
ret = ret + encodeUtil(code[i], "", root); }
return ret;
}
std::string encodeUtil(char ch, std::string code, Node *m)
{
if (m == NULL) {
return " ";
}
if (ch == m -> ch) {
return code;
}
std::string ret1 = encodeUtil(ch, code + "0", m -> left);
if (ret1.compare(" ") != 0)
return ret1;
std::string ret2 = encodeUtil(ch, code + "1", m -> right);
if (ret2.compare(" ") != 0)
return ret2;
return " ";
}
std::string serialize() {
return serializeUtil(root, "");
}
std::string serializeUtil(Node *root, std::string ret)
{
if (root == NULL) {
return ret + "/";
}
ret = ret + root -> ch;
ret = serializeUtil(root -> left, ret);
ret = serializeUtil(root -> right, ret);
return ret;
}
};
int main() {
std::string input;
while (true) {
std::cout << "Input string: ";
std::getline (std::cin, input);
if (input.compare("q") == 0)
return 0;
Huffman *h = new Huffman();
h->build_tree(input);
std::cout << std::endl;
std::cout << h->encode(input) << std::endl;
std::cout << h->serialize() << std::endl;
delete h;
}
}
#endif
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.