c++ - 解码哈夫曼树

Question

我正在尝试解码以下形式的哈夫曼树:

001A1C01E01B1D

我正在使用此处的实现:Efficient way of storing Huffman tree以上述形式对树进行编码并对其进行解码。

这是我的实现:

HuffmanNode* HuffmanTree::decodeTree(string tree, int idx) {
    cout << idx << endl;
    if (tree[idx] == '1') {
        idx += 2;
        return new HuffmanNode(tree[idx - 1]);
    }
    else {
        if (idx != tree.length() - 1) {
            idx++;
            HuffmanNode* leftChild = decodeTree(tree, idx);
            idx++;
            HuffmanNode* rightChild = decodeTree(tree, idx);
            return new HuffmanNode(leftChild, rightChild);
        }
        else
            return new HuffmanNode(tree[idx]);
    }
}

当函数展开时(在“return new HuffmanNode(tree[idx - 1]];”上)，我在写一个位置时遇到了访问冲突，我希望最终的返回将是树，但经过进一步检查，情况似乎并非如此。谁能给我一些指示？ (没有双关语意)

Answer 1

您的代码的问题是 idx 在递归运行中没有被修改。将其作为 int & 传递给函数:HuffmanNode* HuffmanTree::decodeTree(string tree, int &idx)

您的代码中还有一个错误，这使得它成为段错误:而不是

if (tree[idx] == '1') {
    idx += 2;
    return new HuffmanNode(tree[idx - 1]);
}

你应该有

if (tree[idx] == '1') {
    ++idx;
    return new HuffmanNode(tree[idx]);
}

另一个 1 被添加到第二个 block 中的索引:

idx++;
HuffmanNode* leftChild = decodeTree(tree, idx);
idx++;
HuffmanNode* rightChild = decodeTree(tree, idx);

此外，考虑做一件事，类似于您链接到的示例:传递对字符串迭代器(或 istringstream 或其他流)的引用，并且不传递索引: HuffmanNode* HuffmanTree::decodeTree(std::string::const_iterator &tree)。

此外，如果树的格式正确，您不必像 if (idx != tree.length() - 1) 这样的检查。您仍然可以在函数的开头执行此操作以检查输入中的错误，并检查当前符号是 '0' 还是 '1'。