My tree traversal keeps crashing my program

[rofln]

Hello.

I am currently working on a huffman code program for my class. As of right now, I am currently in the development/debugging stage. I've got the whole thing pretty much covered, but I am having trouble with my tree traversal. I am trying to do an inorder traversal but everytime my program runs, it crashes when I tell it to traverse. My tree making algorithm is fine, but there is something wrong with my traversal algorithm. Code is 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)
{
    if(nde == NULL)
        return;
    else
    {
        traverse(nde->left);
        cout << nde->frequency << endl;
        traverse(nde->right);
    }
}

Here is my node class:

#ifndef NODE_H
#define NODE_H

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

#endif

And its source file:

#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 = NULL;
}

It compiles just fine but I am just getting through the kinks. If anyone can provide insight, that would be much appreciated! Thanks!

[Unimportant]

It may be in your best interest to add a default constructor.
Node::Node() : frequency(0), left(NULL), right(NULL), letter(0) { }

void traverse(Node * node)
{ // NULL pointers equal false
  if(node)
  { // This may not output in the order you expect.
    cout << node->frequency << endl;
    traverse(node->left);
    traverse(node->right);
  }
}

[rofln]

Did both of those. Now if I choose that traversal, it starts to traverse but crashes. Here's the console output.

Ramm. Stein. Ein mensch brennt!
R - Frequency: 1
a - Frequency: 1
S - Frequency: 1
E - Frequency: 1
s - Frequency: 1
c - Frequency: 1
h - Frequency: 1
b - Frequency: 1
r - Frequency: 1
! - Frequency: 1
- Frequency: 1
i - Frequency: 2
. - Frequency: 2
t - Frequency: 2
e - Frequency: 3
m - Frequency: 3
- Frequency: 4
n - Frequency: 5
32
-858993460
Press any key to continue . . .

[rofln]

After using a debugger, it says that there is a segmentation fault right when line 168 runs.

[Unimportant]

I told you how to fix it.

[Gonbe]

My tree making algorithm is fine

It is not fine. You should look into something called "scope". You're using "new" while it's not needed and you're saving pointers to objects that'll get out of scope when the function returns.

[rofln]

@Unimportant: Your fix was didn't work. Perhaps you should read my reply.

@Gonbe: I did realize that the makeTree algorithm was indeed the source of my problem. Now I am trying to figure how to actually implement it again. I was thinking perhaps putting it in main (but differently of course).

[Gonbe]

Now I am trying to figure how to actually implement it again.

I might be able to help there, it's however not clear to me what you're trying to do. Why is a single node in the tree the addition of two frequences? Would your tree only have 2 levels where the top level nodes have the combined frequency of their (2) childs? I'm not even sure if you would technically call that a tree. If you describe what you're trying to create I may provide an example.

[rofln]

Here is what I am trying to do: http://www.siggraph.org/education/materials/HyperGraph/video/mpeg/mpegfaq/huffman_tutorial.html

After some modifications, I had gone to my professor and she suggested I use a priority queue. I have done this but my program is still crashing. Here is the new code, the Node class remains the same.

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.

Code:

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <vector>
#include <queue>
#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);

struct nodeCompare
{
    bool operator() (const Node* left, const Node* right) const {return left->frequency > right->frequency;}
};

int main()
{
    char ch = 0;
    ifstream inFile;
    ofstream outFile;
    int count = 0;
    vector<Node> list;

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

    Node* 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(ch);
            vec.push_back(temp);
        }
        else if(!checkList(ch, vec))
        {
            Node temp(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)
{   
    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();
}

void traverse(Node *nde)
{
    if(nde->left)
        traverse(nde->left);
    cout << nde->frequency << endl;
    if(nde->right)
        traverse(nde->right);
}

[rofln]

GOT IT! All I had to do was make the left and right pointers const and get rid of my sort algorithm!

[Gonbe]

Cool! I was about to post this as a quick little example but good to hear you've managed to sort it out! I tried to keep it as much like the original as I could, although I ended up changing too much I guess. The steps are roughly the same atleast.

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

class Node
{
    public:
        Node(const char ch);
        Node(Node* const l, Node* const r);

        unsigned int get_frequency      () const;
        char         get_letter         () const;
        void         traverse           () const;
        void         increment_frequency();

    private:
        char    letter;
        unsigned int frequency;
        Node*   left;
        Node*   right;
};


void Node::increment_frequency()
{
    frequency++;
}

void Node::traverse() const
{
    // TODO: Provide some callback parameters that will be called for every node. Simple printf for now.

    // First traverse the left sub-tree, if present..
    if (left != NULL) left->traverse();

    // .. then print this node ..
    cout << "[Node] Letter: " << letter << ", frequency: " << frequency << ".\n";

    // .. and finally traverse the right sub-tree.
    if (right != NULL) right->traverse();
}

unsigned int Node::get_frequency() const
{
    return frequency;
}

char Node::get_letter() const
{
    return letter;
}

Node::Node(const char ch)
    : letter(ch), frequency(1), left(NULL), right(NULL)
{
}

Node::Node(Node* const l, Node* const r)
    : letter('*'), left(l), right(r)
{
    frequency = (l->get_frequency() + r->get_frequency());
}


void update_nodes(vector<Node*>& nodes, const char letter)
{
    for (unsigned int i = 0; i < nodes.size(); i++)
    {
        if (nodes[i]->get_letter() == letter)
        {
            nodes[i]->increment_frequency();
            return;
        }
    }
    nodes.push_back(new Node(letter));
}

bool compare_node_by_frequency (const Node* l, const Node* r)
{
    // 'l' is to be placed before 'r' if l's frequency is lower than r's frequency.
    return (l->get_frequency() < r->get_frequency());
}

int main()
{
    ifstream      inFile;
    vector<Node*> nodes;
    char          ch       = 0;

    inFile.open("message.txt");

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

    while (inFile.good())
    {
        // Might want to filter out spaces, newlines, etc.
        ch = inFile.get();
        update_nodes(nodes, ch);
    }

    // Convert the list of nodes into a tree. (should put it in a function or w/e)
    while(nodes.size() > 1)
    {
        // Sort the nodes by frequency. (Later modify this to insert instead of sort for performance)
        sort(nodes.begin(), nodes.end(), compare_node_by_frequency);

        Node* new_node = new Node(nodes[0], nodes[1]);

        nodes.erase(nodes.begin(), nodes.begin() + 2);
        nodes.push_back(new_node);
    }

    // There is only one node left. (the root) Traverse it.
    nodes[0]->traverse();

    // Close the file. Also delete the dynamic memory here. I'm lazy.
    inFile.close();

    return 0;
}

[rofln]

Hit another wall :(

I have created a function in order to generate a huffman code for each character, but it's not doing anyting....

Here's the snippet:

void makeCode(Node* tree, vector<Node> &vec, string &huf)
{

    if(tree->right == NULL && tree->left == NULL)
    {
        tree->code = huf;
    }
    if(tree->left != NULL)
    {
        makeCode(tree->left, vec, huf + "0");
    }
    if(tree->right != NULL)
    {
        makeCode(tree->right, vec, huf + "1");
    }
}

I've added a string to main in order to hold the code. When I run the program, I have set to where I can see the code for each character as well as the string, but nothing shows up. I really do appreciate the patience and time you're putting in. This has been a learning experience for me, let me tell you.

EDIT: It seems that when the function runs, the string does get filled but is emptied when it is complete. Scopes...

[rofln]

Finally managed to get the whole thing sorted out!