Binary tree forming wrong

Question

It seems that my code for creating a binary tree for a huffman coding program is flawed. I can't figure out why, but when I exam the root node in the debugger the left node points to the letter N and the right node points to a parent node. The parent node's left node points to the letter N, while the right node points to a parent node. That parent node's left child is the letter N, while... (you see where this is going). This is the code where the problems are:

huff_sort(nodes); // sort nodes by weight

    //-------BUILDING TREE------
    while(nodes->size() != 1){ //Sorts nodes by weight and then removes two of them and replaces them with one
        int w= (**beg).weight + (**(beg+1)).weight;
        Node* p = new Node;
        p->set_node(w, '*', *nodes->begin(), *(nodes->begin()+1)); //making it the parent node of the two lowest nodes
        nodes->erase(nodes->begin(), nodes->begin()+2);
        unsigned int i = 0;
        while(w > (*nodes)[i]->weight && i <= nodes->size()){ //finds where to insert the parent node based on weight
            i++;
        }
        if(i > nodes->size()) //if it needs to be inserted at the end
            nodes->push_back(p);
        else
            nodes->insert(nodes->begin()+i, p);
        delete p;
    }

From previous debugging, I know that the huff_sort function works.

std::map is implemented as a sorted binary tree: en.cppreference.com/w/cpp/container/map — Man of One Way
@ManofOneWay I don't see how that could be implemented for use in a Huffman coding algorithm, since I don't see a way to manually traverse the tree. Anyway, I'm doing this as a learning opportunity, otherwise I would just use a library to compress the files. — sinθ
You can use a custom comparator to order the elements in the way you want them to be ordered. You can traverse the tree using iterators as usual. — Man of One Way

Alan Stokes Alan Stokes · Accepted Answer · 2012-07-25T07:04:58

At the end of the loop you do delete p which invalidates the pointer and frees the node you just inserted.

Binary tree forming wrong

1 Answers