CODEWITHSUNDEEP
c++recursiontreehuffman-code
Twhite1195
Twhite1195

Reputation: 351

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

Upvotes: 0

Views: 307

Answers (1)

Beta
Beta

Reputation: 99094

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);

Upvotes: 2

Related Questions