解码哈夫曼树

我试图解码格式的哈夫曼树：我使用的是实施这里找到解码哈夫曼树

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

我得到一个访问冲突写的位置时的功能开，（在 “回归新HuffmanNode（树[IDX - 1]）;”），我希望最终的回报会成为树的根源，但经过进一步检查，似乎并非如此。任何人都可以给我一些指点吗？（没有双关语意）

来源

2015-04-02 Taylor Bishop

你期待IDX的递归调用之间共享？如果是这样的话，你需要将它作为参数列表中的参考。你也可以做一些额外的安全检查（有适当的错误）。例如，它会被任何以“1”结尾的字符串绊倒。 – Dave 2015-04-02 19:06:39

与您的代码的问题是，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是被添加到索引第二块内：

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'。

来源

2015-04-02 19:56:42 Kolmar

如果它的格式正确，你的意思是什么？它必须有某种基本情况，它不会停止调用该函数，并可能超出字符串的末尾？我尝试过使用迭代器，但我遇到了同样的问题 - 我无法知道输入流的结束时间，以及我是否完成了在树中的读取。 – 2015-04-05 20:44:13

@TaylorBishop不，如果实现中没有错误，并且编码的字符串是正确的，则此算法无法读取超出字符串的末尾。看看你链接的帖子。可以将实际数据放在与树相同的字符串/数组中。因此，您可以从解码树的索引开始解码数据。编码树中的所有内部节点都标记为0，叶子标记为1.在读取标记为1的节点之后，您不再进行递归调用。这是基本情况。 – Kolmar 2015-04-05 22:04:38

解码哈夫曼树

回答

相关问题