Segmentation fault when trying to traverse tree

[rofln]

Hello.

I am currently working on a Huffman code program for one of my classes. I've been working for a while now but I have hit a wall. I have gone all the way up to the point where I have created a tree but when I try to traverse it, the program crashes and says there is a segmentation fault. After running the debugger, the error occurs when I try to traverse to the left node (Line 170). The code I have below is not completely finished, I ran across the issue while testing to see that it works. See the code below:

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <vector>
#include "Node.h"

using namespace std;

void fillList(char* sent, int size, vector<Node> &vec);
bool checkList(char ch, vector<Node> vec);
void getFreq(vector<Node> &vec, char* sent, int size);
void sort(vector<Node> &vec);
Node makeTree(vector<Node> &vec);
void traverse(Node *nde);

int main()
{
	char ch = 0;
	ifstream inFile;
	ofstream outFile;
	int count = 0;
	vector<Node> list;
	Node tree = 0;
	
	inFile.open("message.txt");

	if(!inFile)
	{
		cerr << "Unable to open file! Program terminating..." << endl;
		return(EXIT_FAILURE);
	}

	while(inFile.good())
	{
		ch = inFile.get();
		count++;
	}

	inFile.close();

	char* msg = new char[count];

	inFile.open("message.txt");

	if(!inFile)
	{
		cerr << "Unable to open file! Program terminating..." << endl;
		return(EXIT_FAILURE);
	}

	while(inFile.good())
	{
		inFile.getline(msg, count);
	}

	cout << msg << endl;


	fillList(msg, count, list);
	getFreq(list, msg, count);
	sort(list);

	for(size_t i = 0; i < list.size(); i++)
	{
		cout << list[i].letter << " - Frequency: " << list[i].frequency << endl;
	}

	tree = makeTree(list);
	traverse(&tree);

	delete[] msg;
}

void fillList(char* sent, int size, vector<Node> &vec)
{
	char ch = 0;

	for(int i = 0; i < size; i++)
	{
		ch = sent[i];
		
		if(vec.size() == 0)
		{
			Node *temp = new Node(ch);
			vec.push_back(*temp);
		}
		else if(!checkList(ch, vec))
		{
			Node *temp = new Node(ch);
			vec.push_back(*temp);
		}
	}
}

bool checkList(char ch, vector<Node> vec)
{
	for(size_t i = 0; i < vec.size(); i++)
	{
		if(ch == vec[i].letter)
		{
			return 1;
		}
	}

	return 0;
}

void getFreq(vector<Node> &vec, char* sent, int size)
{
	for(size_t i = 0; i < vec.size(); i++)
	{
		int count = 0;

		for(int j = 0; j < size; j++)
		{
			if(vec[i].letter == sent[j])
			{
				count++;
			}
		}

		vec[i].frequency = count;
	}
}

void sort(vector<Node> &vec)
{
	for(size_t i = 0; i < vec.size() - 1; i++)
	{
		for(size_t j = i + 1; j < vec.size(); j++)
		{
			if(vec[i].frequency > vec[j].frequency)
			{
				Node temp = vec[i];
				vec[i] = vec[j];
				vec[j] = temp;
			}
		}
	}
}

Node makeTree(vector<Node> &vec)
{
	while(vec.size() > 1)
	{
		Node min1 = vec[0];
		Node min2 = vec[1];

		vec.erase(vec.begin() + 0);
		vec.erase(vec.begin() + 0);
		Node* temp = new Node(min1.frequency + min2.frequency);
		temp->left = &min2;
		temp->right = &min1;
		vec.push_back(*temp);
		delete temp;
		sort(vec);
	}

	return vec[0];
}

void traverse(Node *nde)
{
	Node* tp = nde;

	if(tp == NULL)
		return;
	else
	{
		traverse(tp->left);
		cout << tp->frequency << endl;
		traverse(tp->right);
	}
}

Node Class:

#ifndef NODE_H
#define NODE_H

class Node
{
	public:
	Node(char ch);
	Node(int freq);
	Node();
	char letter;
	int frequency;
	Node* left;
	Node* right;
};

#endif 

Node Source:

#include "Node.h"
#include <iostream>

using namespace std;

Node::Node(char ch)
	: letter(ch)
{
	left = NULL;
	right = NULL;
}

Node::Node(int freq)
	: frequency(freq)
{
	left = NULL;
	right = NULL;
	letter = 0;
}

Node::Node()
	: frequency(0), left(NULL), right(NULL), letter(0)
{
}

Any insight would be greatly appreciated.

[cire]

void fillList(char* sent, int size, vector<Node> &vec)
{
	char ch = 0;

	for(int i = 0; i < size; i++)
	{
		ch = sent[i];
		
		if(vec.size() == 0)
		{
			Node *temp = new Node(ch);
			vec.push_back(*temp);
		}
		else if(!checkList(ch, vec))
		{
			Node *temp = new Node(ch);
			vec.push_back(*temp);
		}
	}
}

On lines 11 and 16 you allocate a new node dynamically. On lines 12 and 17 you add a copy of those nodes to your vector. On lines 13 and 17 18 you leak the memory you just allocated.

Your makeTree function is completely wrong and is the (indirect) source of your segmentation fault. You know that the makeTree function leaves your vector with one single element. You don't exactly need a traversal function to traverse a single element, do you?

[rofln]

I have corrected the memory leaks by adding delete lines for the fillList function. I just figured out that my makeTree function was indeed the source of my segmentation fault. I was aware that it was leaving my vector with one element. What I was trying to do was create a tree by using those elements and then storing the whole thing in the first element. I thought that I could do this because in order to make the Huffman tree, I had to keep merging the two smallest frequencies together into a single tree and then keep merging trees. But as previously stated, this algorithm is indeed entirely wrong. And to think I was getting close :(

[ne555]

> I have corrected the memory leaks by adding delete lines
vec.push_back( Node(ch) );


Also, keep in mind that vector may reallocate the elements, so the pointers would be meaningless. Use indexes instead

Edit: in `maketree()'
temp->left and temp->right are pointing to local variables that will die at the end of the function.

[rofln]

Okay, so I got rid of the dynamic allocation in the fill list function and just created Node variables:

void fillList(char* sent, int size, vector<Node> &vec)
{
	char ch = 0;

	for(int i = 0; i < size; i++)
	{
		ch = sent[i];
		
		if(vec.size() == 0)
		{
			Node temp(ch);
			vec.push_back(temp);
		}
		else if(!checkList(ch, vec))
		{
			Node temp(ch);
			vec.push_back(temp);
		}
	}
}

And now I am being lead to believe that in order to make the tree, I am going to have to put the function inside of main but implement it in a different way?

[rofln]

I spoke to my professor and she recommended that I use a priority queue of Node pointers. I have done this and now the program is still crashing. Here is my updated makeTree function:

Node* makeTree(vector<Node> &vec)
{	
	priority_queue<Node*, vector<Node*>, nodeCompare> tree;

	for(size_t i = 0; i < vec.size(); i++)
	{
		Node* temp = &vec[i];
		tree.push(temp);
	}

	while(tree.size() > 1)
	{
		Node* min1 = tree.top();
		tree.pop();

		Node* min2 = tree.top();
		tree.pop();

		Node* temp = new Node(min1->frequency + min2->frequency, min2, min1);
		tree.push(temp);
	}

	return tree.top();
}

EDIT: It's strange now. It will run in command prompt but will not run in Visual studio. In command prompt it while show the frequency of the root then return to the OS.

[cire]

One issue is that the tree is composed of nodes that are in a vector and nodes that have been new'd. The ones that have been new'd need to be individually deleted before the program ends. That poses a small difficulty. At first one might be tempted to resize the vector and feed the tree a pointer to a new Node in the vector to avoid the manually managed memory, but that could result in the vector memory being reallocated, which wouldn't bode well for the program. On the other hand, if you used a std::deque to contain the nodes rather than a vector, that wouldn't be an issue (although the vector is fine for the priority_queue container.)

Node* temp = new Node(min1->frequency + min2->frequency, min2, min1);

You don't have this constructor in your code for Node above. If the first Node* is the left link, shouldn't it be the smallest one (min1)? Just seems a bit counter-intuitive to me.

Other than those issues, makeTree looks alright to me. (I can't say that I've actually put it in a compiler and did any testing, though.)