struct node {
float weight;
char value;
node* left_child;
node* right_child;
};
void get_codes(node tree, std::string code, std::map<char, std::string> &codes)
{
if(!tree.left_child && !tree.right_child) // leap node
codes[tree.value] = code;
else
{
get_codes(*tree.left_child, code + "0", codes);
get_codes(*tree.right_child, code + "1", codes);
}
}
int main()
{
std::string test {"this is an example of a huffman tree"};
std::vector<char> alphabet = get_alphabet(test);
std::vector<float> weights = get_weights(test, alphabet);
std::priority_queue<node, std::vector<node>, is_node_greater> heap;
for(int i=0; i<alphabet.size(); i++)
{
node x;
x.weight = weights[i];
x.value = alphabet[i];
x.left_child = nullptr;
x.right_child = nullptr;
heap.push(x);
}
while(heap.size() > 1) {
node fg = heap.top(); heap.pop();
node fd = heap.top(); heap.pop();
node parent;
parent.weight = fg.weight + fd.weight;
parent.left_child = &fg;
parent.right_child = &fd;
heap.push(parent);
}
node tree = heap.top(); // our huffman tree
std::map<char, std::string> codes;
get_codes(tree, "", codes);
}
In the first loop, I build a heap (a priority queue) containing all the leap nodes, ie no left child, no right child (nullptr).
In the second loop, while the heap contains more than one node, I take the two with the smallest weights and I create a parent node with these two nodes as children. The parent node's weight is the sum of the two children's.
Then I have my huffman tree, and I have to get huffman codes. That is to say, I need to get a binary code for each leap node assuming bit '0' represents following the left child and bit '1' represents following the right child.
That's what my function get_codes should do, and where the crash occurs. It never enters the 'if' statement so recursivity never stops, so I think either it never comes to leap nodes but it should because each time the function is called on a child tree ; or the leap nodes/nullptr have been lost..? I'm new at C++ so I'm not very experienced with pointers, but this is how I would do the function in an other language.