c++ - 编码霍夫曼二叉树

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
        }
     }

在节点不是叶子的情况下，一定有你打算做的事情。也许递归？

(根据评论)您可能正在使用霍夫曼树的一种变体，在这种变体中您可以保证每个节点都是叶节点或有一个叶节点。如果你能保证，那么上面的就无所谓了(如果发生了抛出异常就好了)。然而，现实世界中的霍夫曼树不具备此属性。

---

当一个 child 是叶子而另一个不是你的目标字母时，你尝试设置一个新的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;
    }