编码哈夫曼二叉树

Question

我正在尝试编写一个函数，它需要一个霍夫曼树和一个字符。然后它应该对角色进行编码并将其返回。

至今代码：

string encode(NodePtr root, char letter) 
{ 
    string encode_str; //a string which will store the encoded string 
    NodePtr tempNode = root; //Initialize a new Huffman to be used in this function 
    NodePtr tempLeft = root->left; 
    NodePtr tempRight = root->right; 

     //A while loop that goes on until we find the letter we want 
     while((tempLeft->letter != letter) || (tempRight->letter != letter)) 
     { 
     if((tempRight->is_leaf()) && (tempRight->letter == letter)) //check if is leaf and is letter 
     { 
       encode_str = encode_str + '1'; 
     } 
     else if ((tempLeft->is_leaf()) && (tempLeft->letter == letter)) //check if is leaf and is letter 
     { 
      encode_str = encode_str + '0'; 
     } 
     else if ((tempRight->is_leaf()) && (tempRight->letter != letter)) //check if is leaf and is NOT letter 
     { 
      tempNode = root->left; 
      tempLeft = tempNode->left; 
      tempRight = tempNode->right; 
      encode_str = encode_str + '0'; 
     } 
      else if ((tempLeft->is_leaf()) && (tempLeft->letter != letter)) //check if is leaf and is NOT letter 
     { 
      tempNode = root->right; 
      tempLeft = tempNode->left; 
      tempRight = tempNode->right; 
      encode_str = encode_str + '1'; 
     } 
     }  

    return encode_str; 
} 

这至今还没有工作，调试并没有帮助我满意。任何人都可以帮助我，或者至少告诉我我的想法是否正确。

Answer 1

如果没有tempLeft也不tempRight是叶，你有一个无限循环：

while((tempLeft->letter != letter) || (tempRight->letter != letter)) 
    { 
     if((tempRight->is_leaf()) && 
      (tempRight->letter == letter)) 
     { 
      // no 
     } 
     else if ((tempLeft->is_leaf()) && 
       (tempLeft->letter == letter)) 
     { 
      // no 
     } 
     else if ((tempRight->is_leaf()) && 
       (tempRight->letter != letter)) 
     { 
      // no 
     } 
     else if ((tempLeft->is_leaf()) && 
       (tempLeft->letter != letter)) 
     { 
      // no 
     } 
    } 

必须有你想要的情况下做的节点在哪里并不令人不满意。也许递归？

（根据注释）您可能正在使用哈夫曼树的变体，您可以在其中确保每个节点都是叶子或有一个叶子。如果你可以保证这一点，那么上面的内容并不重要（如果它发生，抛出异常是很好的）。然而，现实世界的霍夫曼树没有这个属性。

---

当一个孩子是叶，另一种是不是你的目标字母，您尝试设置一个新的tempNode，tempLeft和tempRight周边循环的下围棋。

else if ((tempRight->is_leaf()) && 
      (tempRight->letter != letter)) 
    { 
     tempNode = root->left; 
     tempLeft = tempNode->left; 
     tempRight = tempNode->right; 
     encode_str = encode_str + '0'; 
    } 

但是，因为你永远不修改root，tempNode = root->left将始终设置tempNode同一节点。

您可能想要tempNode = tempNode->left。

---

为了避免码重复，你可以移动

tempLeft = tempNode->left; 
tempRight = tempNode->right; 

...是这种情况发生在while()循环的第一件事。

---

你说，调试并没有帮助。你真的在调试器中运行它吗？

编写一个单元测试，设置你的树;验证树实际上包含你打算的内容;并用一个字母调用该函数。决定你认为执行应该如何进行。现在在调试器中运行代码，逐步完成它。当它停止了你认为应该做的事时，你就能够推断出原因。

---

实现霍夫曼编码的一种常见方式是有叶节点的数组，这样你就可以通过简单的数组访问到达节点：

NodePtr nodeA = nodes[0]; 

...并且在每个节点中都有一个指向父节点的指针，并且有一个字段指示它是左侧还是右侧的子节点，以便您可以轻松遍历树，从叶到树，构建代码（反向）：

string code = ""; 
    NodePtr node = nodeA; 
    while(node->parent != NULL) { 
     code = node->code + code; 
     node = node->parent; 
    }