我的哈夫曼编码方法哪里出错了？

Question

我正在尝试编写霍夫曼字符串编码算法。

我的解决方案是这样工作的：

由于字符串中的每个字母都有与之关联的特殊二进制代码，因此搜索二叉树并在找到字母时将其添加到带有二进制代码的映射中。 (这里是我出错的地方)
迭代字符串，并为每个字母关联与映射字母的键关联的值。

我没有在某处打印树，即使很难帮助你帮助我，但这是我得到的字符串 abracadabra，以及我应该得到的:

正确代码：000010000110110101111101011000111110110100111011101100101101110000110000110111100101111101010010

我得到了什么： 00001000111011010110101111010101100011101011010

这是我的代码：

#include <algorithm>
#include <map>

string codes = "";

void getMapCharBinaryCode(Node root, string &prefix, map <char, string> &m){
    if(!root) return;
    if(root->value){
        if(!m.count(root->value)){
            m[root->value] = prefix;
            prefix = "";
        } 
    }
    if(root->leftChild){
        getMapCharBinaryCode(root->leftChild, prefix += "0",m);
    }
    if(root->rightChild){
        getMapCharBinaryCode(root->rightChild, prefix += "1",m);
    }
   
}

string encode(string text, Node tree){
    // text is "abracadabra"
    // create map for each char -> binary code
    map<char, string> m;
    string prefix = "";
    getMapCharBinaryCode(tree, prefix, m);
    
    // iterate on text and assign each letter with binary code from map
    for(int i = 0; i < text.size(); i++) {
        codes += m[text[i]];
    }
    return codes;
}

Answer 1

当您使用 prefix = "" 保存一片叶子时，您正在破坏 prefix 中的代码，当您从树上掉下来并转到下一个分支时需要代码。

您可以为 prefix 维护一个存储区域，通过引用传递它。但是你需要在树上上下移动时管理 prefix 的长度，并且你需要不添加 0，然后添加 1 到那用于两个分支，为右分支添加 01 而不是 1.

作为起点，您应该只按值传递 prefix，这会生成副本，但在管理时不需要小心。删除 & 并将 prefix += 替换为 prefix +。去掉 prefix = ""，它什么都不做。

我的哈夫曼编码方法哪里出错了？

Where does my Huffman encoding method go wrong?

c++

algorithm

huffman-code