霍夫曼解码算法

Question

解码时，我无法构建哈夫曼树的结构。

现在我正在编码的树，如果它有子码使前缀0，如果它没有孩子使它1。

例如，像(a,b,c,d)树会被编码为001a1b01c1d及其Huffman编码是

00|01|10|11 

注：|是为清晰添加的，实际上并不是在头中。

这里的图形形式的树：

/\ 
    /\ /\ 
    a b c d 

现在，当我试图重建使用001a1b01c1d树，我有麻烦的问题是重新创建树正确，因为我不能确定检查什么当回到树上时（走多远）。

Here is the code the index was only added just to try the word 'random' obviously it doesn't work for other cases. I am thinking of using the depth of the tree somehow

void Tree::build(std::queue<char> encodedHeader) { 
    char currentChar; 
    this -> thisRoot = new HCNode(0, '\0',0,0,0); 
    HCNode * newRoot = new HCNode (0,'\0',0,0,0); 
    HCNode * childZero = new HCNode (0, '\0', 0,0,0); 
    HCNode * childOne = new HCNode (0, '\0', 0,0,0); 
    childZero -> p = newRoot; 
    childOne -> p = newRoot; 
    newRoot -> c0 = childZero; 
    newRoot -> c1 = childOne; 
    this -> foreverRoot = newRoot; 

    while(!header.empty()) { 
     currentChar = header.front(); 
     header.pop(); 
     if(currentChar != '\n') { 
      if (currentChar == '0') { 
       HCNode * childZero = new HCNode (0, '\0', 0,0,0); 
       HCNode * childOne = new HCNode (0, '\0', 0,0,0); 
       child0 -> p = newRoot; 
       child1 -> p = newRoot; 
       newRoot -> c0 = childZero; 
       newRoot -> c1 = childOne; 

       currentChar = header.front(); 
       while (currentChar == '0') { 
        newRoot = newRoot -> c0; 
        header.pop(); 
        currentChar = header.front(); 
        HCNode * childZero = new HCNode (0, '\0', 0,0,0); 
        HCNode * childOne = new HCNode (0, '\0', 0,0,0); 
        childZero -> p = newRoot; 
        childOne -> p = newRoot; 
        newRoot -> c0 = childZero; 
        newRoot -> c1 = childOne; 
       } 
      } 
      else { 
       currentChar = header.front(); 
       header.pop(); 

       if(newRoot -> c0 != NULL) { 
        newRoot -> c0 -> symbol = currentChar; 
        newRoot = newRoot -> c1; 
       } 
       else { 
        newRoot -> symbol = currentChar; 
        while(newRoot -> p != NULL && index != 2) { 
         index++; 
         newRoot = newRoot -> p; 
        } 
        index = 0; 
        newRoot = newRoot -> c1; 
       } 
      } 
     } 
    } 

Answer 1

我真的只是写一些代码来做到这一点作为一个练习，你所使用的完全相同的头格式，像我一样。我发现的诀窍是，这是多容易递归实现，如：

Node read_tree(some_input input, string current_code = "") { 
    Node node; 
    if (input.readchar() == '0') { 
     node.left = read_tree(input, current_code + "0"); 
     node.left.parent = node; 
     node.right = read_tree(input, current_code + "1"); 
     node.right.parent = node; 
    } else { 
     node.code = input.readchar(); 
    } 
    return node; 
} 

显然，你需要做的使用自己的更现实的类型类似的东西，但基本的思路应该工作。

Answer 2

首先，我对我的英语非常抱歉（这不是我的母语:-)。 一般建议通过递归来解决树问题，这也是一个很好的建议。 这里是我认为可以工作（我没有测试，所以也许这将需要一些工作）代码：

buildTree(std::queue<char> header, HCNode* node) 
{ 
    char currentChar = header.front(); 
    header.pop(); 
    if(currentChar == '0') 
    { 
      childZero -> p = newRoot; 
      childOne -> p = newRoot; 
      node->c0 = new HCNode (0, '\0', 0,0,0); 
      node->c1 = new HCNode (0, '\0', 0,0,0); 
      node->c0->p = node; 
      node->c1->p = node; 
      buildTree(header, node->c0); // this is the recurtion 
      buildTree(header, node->c1); // this is the recurtion too 
    } 
    else // currentChar == '1' 
    { 
      currentChar = header.front();// currentChar = symbol 
      header.pop(); 
      node-> symbol = currentChar; 
    } 
} 
void Tree::build(std::queue<char> encodedHeader) 
{ 
    this->foreverRoot = new HCNode(0, '\0',0,0,0); 
    buildTree(header, foreverRoot); 
} 

我很希望这将是有益的。祝你好运。