解码霍夫曼树 [英] Decoding Huffman Tree

问题描述

我正在实现一个接受树和编码字符串的函数. 示例:

I am implementing a function that takes in a tree and an encoded string. Example:

decode(*Huffmantree, "10010101010")

我希望此函数返回输入中相对于霍夫曼树输入的编码字符串的解码字符串.

I want this function to return decoded string for the encoded string in the input relative to the Huffman tree input.

我到目前为止的代码:

string decode(NodePtr root, string encoded_str)
{
    string temp = "";
    for (int i = 0 ; i < encoded_str.size() ; i++)
    {
        if (root->is_leaf() == true)
        {
            temp[i] = root->letter;
            //cout << root->letter;
        }
        if (root->left != NULL)
        {
            encoded_str.
        }
        if(root->right != NULL)
        {

        }
    }
    return temp;
}

我难以实现当left或right不为NULL时(即必须继续到下一个节点时)发生的情况.

有什么想法吗?

string decode(NodePtr root, string encoded_str)
{
    string temp = "";
    int i;
    for( i = 0 ; i < encoded_str.size() ; i++)
    {

    if(root == NULL)
    {
        cout<<"error in string"<<endl;
        return temp;
        //cout<<root->letter;
    }
    temp[i] = root->letter;
    if(encoded_str[i] == '0')
    {
        root = root->left;
    }
    else
    {
        root = root->right;
    }
    }
//    for (int i = 0 ; i < temp.size(); i++)
//    {
//        cout<<temp[i];
//    }
//    cout<<endl;
    temp[i]='/0';
    return temp;
}

推荐答案

以下内容可能会有所帮助:

Following may help:

string decode(NodePtr root, string encoded_str)
{
    string res = "";
    NodePtr node = root;
    for (int i = 0; i != encoded_str.size(); ++i)
    {
        if (encoded_str[i] == '0') { // left child
            node = node->left;
        } else { // rigth child
            assert(encoded_str[i] == '1');
            node = node->right;
        }
        if (node->is_leaf() == true)
        {
            res += node->letter;
            node = root;
        }
    }
    return res;
}

这篇关于解码霍夫曼树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！