I'm trying to write a program to build a Huffman tree. I asked about this in the General C++ Programming forum, and got a solution, but I can't use the code as this is for a homework assignment.
The tree is supposed to be like this:
310
/ \
127 183
d / \
64 119
/ \ a
20 44
b c

Note that the numbers are frequencies, with the letters below some of the nodes representing the character.
This is the problem function:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

node buildHuffmanTree()
{
node tempNode, a, b;
while (!nodeVector.empty())
{
std::sort(nodeVector.begin(), nodeVector.end());
a = nodeVector.front();
nodeVector.erase(nodeVector.begin());
b = nodeVector.front();
nodeVector.erase(nodeVector.begin());
tempNode.left = &a;
tempNode.right = &b;
tempNode.frequency = a.frequency + b.frequency;
nodeVector.push_back(tempNode);
std::sort(nodeVector.begin(), nodeVector.end());
if (nodeVector.size() == 1) {break;}
}
return tempNode;
}
 
Here is the
node
struct:
1 2 3 4 5 6 7 8 9

struct node
{
char data;
int frequency;
std::bitset<1> code;
node *left;
node *right;
bool operator<(const node &temp) const {return frequency < temp.frequency;}
};
 
nodeVector,
is a vector of these structs, implemented as a global variable.
I have to extract the two nodes with frequencies of minimum value, create a new node that points to each of them, remove the two nodes from the vector, and add the frequencies.
This is what the function is returning:
310
/ \
127 183
d / \
127 183
d / \
127 183
d / \
127 183
d / \
127 183
d / \
[...]

And so on, for many more levels.
Is there an easy way to fix this function?
Thanks!