Huffman Tree, recursive function crashes (pointers are not relayed correctly)

106 views Asked by At
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.

0

There are 0 answers