Fixing a function to build a Huffman tree

[andrew241]

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:

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:

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!

[TheIdeasMan]

Hi andrew241,

Unfortunately, reposting your problem in the beginners section doesn't necessarily mean someone will post simpler code :)

Both respondents have very solid knowledge bases, can you carefully look at the advice given in the other topic and apply it to your code?