Huffman Coding Creating Tree C++

Question

The code is a part of bigger solution. When I have only one element in prioriQueue, lastLeft and lastRight are nullptr. Any idea how to change this algorithm to work corectly with only one element, or some tips how to write it better? Problem is in line with comment "HERE IS A PROBLEM".

 std::shared_ptr<Leaf> HUFFMAN::TreeGenerating()
    {
        std::shared_ptr<Leaf> lastLeft = nullptr; // addr of last left child
        std::shared_ptr<Leaf> lastRight = nullptr; // addr of last right child

        while (!prioriQueue.empty())
        {
            std::shared_ptr<Leaf> rightChild = std::make_shared<Leaf>();
            std::shared_ptr<Leaf> leftChild = std::make_shared<Leaf>();
            std::shared_ptr<Leaf> nRoot = std::make_shared<Leaf>();

            if (prioriQueue.size() == 1) // getting last element from prioriQueue, this if end algorithm
            {
                *nRoot = getElement();
                nRoot->setLeftChild(lastLeft);
                nRoot->setRightChild(lastRight);

                nRoot->setFreq(lastLeft->getFreq() + lastRight->getFreq()); // HERE IS A PROBLEM !!
                nRoot->setValue(0);
                return nRoot;
            }
            else 
            {
                *leftChild = getElement();
                *rightChild = getElement();

                nRoot->setLeftChild(leftChild);
                nRoot->setRightChild(rightChild);
                nRoot->setFreq(leftChild->getFreq() + rightChild->getFreq());
                nRoot->setValue(0);

                lastLeft = leftChild;
                lastRight = rightChild;

                InsertIntoQueue(*nRoot);
            }
        }

}

Off topic: It looks like you are misusing `std::shared_ptr`. Recommend a a read of [Which kind of pointer do I use when?](http://stackoverflow.com/questions/8706192/which-kind-of-pointer-do-i-use-when) — user4581301, Jan 04 '17 at 21:09
I can't use Unique_ptr becouse of operation u don't see in my post. — ArekJastrzebski, Jan 04 '17 at 21:25

score 0 · Accepted Answer · answered Jan 04 '17 at 22:28

I'd drop this as a comment because OP's question is missing too much information for a proper answer, but it's too complex for a comment. Note the code is totally untested because too many assumptions would be required.

OP has greatly over-complicated. All that is needed is something along the lines of

std::shared_ptr<Leaf> HUFFMAN::TreeGenerating()
{
    if (!prioriQueue.empty())
    {
        while (prioriQueue.size() > 1)
        {
            std::shared_ptr<Leaf> node = std::make_shared<Leaf>(getElement(), 
                                                                getElement());
            InsertIntoQueue(node);
        }
        return (getElement());
    }
    else
    {
        // handle the empty case
    }
}

with the Leaf constructor something along the lines of:

Leaf::Leaf(std::shared_ptr<Leaf> right, 
           std::shared_ptr<Leaf> left)
{
    rightChild = right;
    leftChild = left;
    freq = right->freq + left->freq
}

or using a Member Initializer List

Leaf::Leaf(std::shared_ptr<Leaf> right, 
           std::shared_ptr<Leaf> left):
    rightChild(right),
    leftChild(left),
    freq(right->freq + left->freq)
{
}

I also strongly recommend reconsidering this abuse of std::shared_ptr.

Huffman Coding Creating Tree C++

1 Answers1