需要帮助编码霍夫曼树

Question

我一直在尝试对霍夫曼树进行编码，但我不明白为什么我得到的二进制密钥都是错误的。树是正确完成的，所以它一定是我的 Binary Keys 方法的问题。

这是我用于编码的代码：

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: 00

P: 01

E: 010

A: 0110

T: 01110

SPACE: 011110

S: 011111

Answer 1

在此处查看您对 key 所做的操作：

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

在树的顶部，有一个左儿子，其字符为 null，因此您将 '0' 附加到 key，然后使用该键探索右子树。

一个简单的修复：

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

需要帮助编码霍夫曼树

Need help encoding a huffman tree

c++

recursion

tree

huffman-code