Twhite1195 Twhite1195 - 1 month ago 7
C++ Question

Need help encoding a huffman tree

Iv'e been trying to encode a Huffman tree, but I can't figure out why the Binary keys I get are all wrong. The tree is done correctly, so it's got to be an issue with my Binary Keys method.

Here's the code I'm using for encoding:

void Tree::CreateBinary(Node *r)
{
if(r==nullptr)
{
cout << "empty Tree" << endl;
}
else
{
if (r->character != NULL)
{
Binary(root, "", r->character);
}

CreateBinary(r->LeftSon);
CreateBinary(r->RightSon);
}

}

void Tree::Binary(Node *r, string key, char character)
{

if (r->LeftSon == NULL && r->RightSon == NULL && r->character == character)
{
r->key = key;
cout << r->character << ": " << r->key << endl;
}

if (r->LeftSon != NULL)
{
if(r->LeftSon->character!=NULL && r->LeftSon->character!=character)
{
Binary(r->LeftSon, key, character);
}else
{
key = key + "0";
Binario(r->LeftSon, key, character);
}

}
if (r->RightSon != NULL)
{
key = key + "1";
Binary(r->RightSon, key, character);
}

}


I've been using this tree as example:
Huffman Tree

and when I try to encode it I get these keys:

I: 00

P: 01

E: 010

A: 0110

T: 01110

SPACE: 011110

S: 011111

Answer

Look at what you do to key here:

if (r->LeftSon != NULL)
{
    if(r->LeftSon->character!=NULL && r->LeftSon->character!=character)
    {
        Binary(r->LeftSon, key, character);
    }else
    {
        key = key + "0";
        Binario(r->LeftSon, key, character);
    }

}
if (r->RightSon != NULL)
{
    key = key + "1";
    Binary(r->RightSon, key, character);
}

At the top of the tree, there is a left son whose character is null, so you append '0' to key, then explore the right sub-tree with that key.

A simple fix:

Binario(r->LeftSon, key+"0", character);