Huffman tree - generating huffman codes

[vdsf]

I'm trying to code a traversal function for a huffman tree that will generate the code dictionary containing the binary codes for each letter in the tree. Once it hits a leaf node I want to insert the character and a QBitArray into the QMap that I pass in.

The part I am confused about is how I can build up the QBitArray before inserting it with the character into the QMap.

Here is my code for the function so far.

template <class CollectionType, class UnitType>
void HuffmanTree<CollectionType, UnitType>::traverse(Node* root, QMap<UnitType, QBitArray>* codes) const
{

        if(root->leftChild == NULL)
        {
                qDebug() << "Character: " << root->data[0];

                //codes->insert(root->data[0], );
        }
        else
        {
                traverse(root->leftChild, codes);

                traverse(root->rightChild, codes);
        }
}

[vdsf]

Ok I came up with a solution, it seems kind of messy though.

template <class CollectionType, class UnitType>
void HuffmanTree<CollectionType, UnitType>::traverse(Node* root, QMap<UnitType, QBitArray>* codes, QString codeString) const
{

        if(root->leftChild == NULL)
        {
            QBitArray codeArray;

                for (int i = 0; i < codeString.length(); i++)
                {

                    if (codeString[i] == '0')
                    {
                        codeArray.resize(codeArray.size()+1);
                        codeArray[i] = false;
                    }
                    else
                    {
                        codeArray.resize(codeArray.size()+1);
                        codeArray[i] = true;
                    }

                }

                codes->insert(root->data[0], codeArray);
        }
        else
        {
                traverse(root->leftChild, codes, codeString+"0");
                traverse(root->rightChild, codes, codeString+"1");
        }
}

[raptr_dflo]

As far as cleanliness, I don't know offhand if you need to resize your QBitArray before assigning into it, but since you know it will be the same length as your input codeString, why not start off with:

QBitArray codeArray(codeString.length());

and skip the resizing completely?

Also, the QBitArray documentation says:

For technical reasons, it is more efficient to use testBit() and setBit() to access bits in the array than operator[]().

Good luck!

[vdsf]

Ok I've changed my code again, I think this is better than what I had originally. What do you think?

template <class CollectionType, class UnitType>
void HuffmanTree<CollectionType, UnitType>::traverse(Node* root, QMap<UnitType, QBitArray>* codes, QBitArray codeArray) const
{

        if(root->leftChild == NULL)
        {
                codes->insert(root->data[0], codeArray);
        }
        else
        {
                int s = codeArray.size();

                codeArray.resize(codeArray.size() +1);
                codeArray.setBit(s, false);
                traverse(root->leftChild, codes, codeArray);

                codeArray.resize(codeArray.size() +1);
                codeArray.setBit(s, true);
                traverse(root->rightChild, codes, codeArray);
        }
}

[raptr_dflo]

I'm not sure how efficient it is to pass copies of the codeArray around, but the feel is nicely recursive. Note that once you've captured codeArray.size() into s, you can use that in your call to codeArray.resize(), and that you only need to resize codeArray once. Otherwise I'm concerned that your codeArray is twice as big as it needs to be, and you're only filling alternating positions in it. Double-check by printing out the size and contents when you insert it at line 7, for a known code value.