Code for Huffman tree not working properly

[andrew241]

I'm trying to write a program building a Huffman tree, but my code isn't working when building the actual tree before doing the binary encoding. The tree is supposed to look like this when debugging:

   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 what I have now:

#include <iostream>	// Allows the use of std::cout >> and cin <<.
#include <string>	// Allows the use of getline().
#include <fstream>	// Allows the use of file I/O.
#include <utility>      // Allows the use of std::bitset.
#include <vector>       // Allows the use of vectors.
#include <algorithm>    // Allows the use of sort.

struct node
{
    char data;
    int frequency;
    std::bitset<1> code;
    node *left;
    node *right;
    bool operator<(const node &temp) const {return frequency < temp.frequency;}
};

std::vector<node> nodeVector;

void getHuffmanData()
{
    std::ifstream inStream;
    int size;
    int tempFrequency;
    char tempData;
    node tempNode;
    
    inStream.open("huff-source.txt");
    
    if (inStream.fail())
    {
        std::cout << "Failure opening input file.\n";
	exit(1);
    }
    
    inStream >> size;
    
    while (inStream.peek() != EOF)
    {
        inStream >> tempData;
        inStream >> tempFrequency;
        tempNode.data = tempData;
        tempNode.frequency = tempFrequency;
        nodeVector.push_back(tempNode);
    }
    inStream.close();
}

node buildHuffmanTree()     // Returns the root node, which points to all
{                           // other nodes.
    node tempNode;
    node tempNode_1;
    node tempNode_2;
    
    while (!nodeVector.empty())
    {
        std::vector<node>::iterator position = std::min_element(nodeVector.begin(),nodeVector.end());
        tempNode_1 = *(position);
        tempNode.left = &tempNode_1;
        nodeVector.erase(position);
        position = std::min_element(nodeVector.begin(),nodeVector.end());
        tempNode_2 = *(position);
        tempNode.right = &tempNode_2;
        nodeVector.erase(position);
        tempNode.frequency = tempNode_1.frequency + tempNode_2.frequency;
        nodeVector.push_back(tempNode);
        if (nodeVector.size() == 1) {break;}
    }
    return tempNode;
}


int main()
{
    node test;
    getHuffmanData();
    test = buildHuffmanTree();
    std::cout << "Press 'Enter' to continue...";
    std::cin.get();
    
    return 0;
}

buildHuffmanTree() is the function that's giving me problems. 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 (while keeping the data intact so they can be pointed to; maybe this is my problem?), and add the frequencies.

This is what the function is returning (set a breakpoint and look at the node returned by buildHuffmanTree()):

   310
  /   \
127   183
 d   /   \
   127   183
    d   /   \
      127   183
       d   /   \
         127   183
          d   /   \
            127   183
             d   /   \
                 [...]

And so on, for many levels.

My input file is as follows:

4
a 119
b 20
c 44
d 127

How would I go about fixing this?

Thanks!

[ne555]

> tempNode.left = &tempNode_1;
All the nodes that you are creating have the same two children.
Those two children die when `buildHuffmanTree()' ends.

[cire]

#include <iostream>
#include <string>	
#include <fstream>
#include <sstream>
#include <vector>       
#include <algorithm>
#include <memory>
#include <iomanip>
#include <cassert>

struct node;
using node_handle = std::unique_ptr<node>;

struct node
{
    char data;
    std::size_t frequency;

    node_handle left;
    node_handle right;

    node(std::size_t freq) : data('\0'), frequency(freq) {}
    node(char ch, std::size_t freq) : data(ch), frequency(freq) {}

    bool operator<(const node& n) { return frequency < n.frequency; }

    bool isLeaf() const { return left == nullptr && right == nullptr;}
};

std::vector<node_handle> extractHuffmanData(std::istream& is)
{
    std::vector<node_handle> data;

    std::size_t frequency;
    char ch;

    while (is >> ch >> frequency)
        data.emplace_back(new node(ch, frequency));

    return data;
}

node_handle buildHuffmanTree(std::vector<node_handle> data)
{
    assert(data.size() > 0);

    auto comp = [](const node_handle& a, const node_handle& b)    
    { 
        return *a < *b; 
    };

    std::sort(data.begin(), data.end(), comp);

    while (data.size() > 1)
    {
        node_handle a(data[0].release());
        node_handle b(data[1].release());
        data.erase(data.begin(), data.begin() + 2);

        node_handle parent(new node(a->frequency + b->frequency));
        parent->left.swap(a);
        parent->right.swap(b);

        auto pos = std::lower_bound(data.begin(), data.end(), parent, comp);
        data.emplace(pos, parent.release());
    }

    return node_handle(data.back().release());
}

void print(const node_handle& node, std::size_t indent_level=0)
{
    if (node == nullptr)
        return;

    const size_t indent_width = 2;
    std::cout << std::setw(indent_width * indent_level) << "";
    std::cout << node->frequency;

    if (node->isLeaf())
        std::cout << " - " << node->data << '\n';
    else
    {
        std::cout << '\n';
        print(node->left, indent_level + 1);
        print(node->right, indent_level + 1);
    }
}

int main()
{
    std::istringstream is
    {
        "a 119\n"
        "b 20\n"
        "c 44\n"
        "d 127\n"
    };

    auto huffmanData = extractHuffmanData(is);
    auto huffmanTree = buildHuffmanTree(std::move(huffmanData));

    print(huffmanTree);
}

http://ideone.com/Bqi35e