霍夫曼编码创建树 C++

Question

该代码是更大解决方案的一部分。当我在 prioriQueue 中只有一个元素时，lastLeft 和 lastRight 是 nullptr。知道如何更改此算法以使其仅与一个元素一起工作，或者一些如何更好地编写它的技巧吗？问题符合注释 "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);
            }
        }

}

Answer 1

我会把它作为评论删除，因为 OP 的问题缺少太多信息无法正确回答，但评论又太复杂了。请注意，代码完全未经测试，因为需要太多假设。

OP 过于复杂了。所需要的只是符合

的东西

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
    }
}

与 Leaf 构造函数类似：

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

或使用 Member Initializer List

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

我还强烈建议重新考虑这种对 std::shared_ptr 的滥用。

霍夫曼编码创建树 C++

Huffman Coding Creating Tree C++

c++

tree

huffman-code