Расшифровка дерева Хаффмана

Я реализую функцию, которая принимает дерево и закодированную строку. Пример:

decode(*Huffmantree, "10010101010")

Я хочу, чтобы эта функция возвращала декодированную строку для кодированной строки на входе относительно входа дерева Хаффмана.

Код у меня так далеко:

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

У меня возникают проблемы с реализацией того, что происходит, когда левый или правый не 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;
}
Источник

3 ответа

Решение

Следующее может помочь:

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;
}
Источник

Это будет один из самых простых кодов, в основном вам нужно проверить, encoded_str действителен или нет.

ОБНОВЛЕНИЕ: Теперь код должен работать.

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

        if(root == NULL ){
            cout<<""not possible , error in encoded_str";
            return temp;
        }


        if(encoded_str[i]=='0')
            root=  root->left ;
        else
            root=  root->right ;


        if(node->is_leaf()){
            temp+=root->letter;
            return temp;
        }
    }

}
Источник

Когда я запускаю это

#include <iostream>
#include<queue>
#include<vector>
#include<iomanip>
#include<string>

using namespace std;


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

        if(root == NULL ){
            cout<< "not possible , error in encoded_str" << endl;
            return temp;
        }


        if(encoded_str[i]=='0')
            root=  root->left ;
        else
            root=  root->right ;


        if(node->is_leaf()){
            temp+=root->letter;
            return temp;
        }
    }

}



int main()
{

    decode(*Huffmantree, "10010101010");


    system("pause");
    return 0;
}

Я получаю некоторые неопределенные ошибки, также была ошибка цитаты в строке 18, которую я изменил.

7   IntelliSense: identifier "NodePtr" is undefined c:\Users\Evan\Documents\Visual Studio 2012\Projects\huffman\huffman\Source.cpp  10  15  huffman
8   IntelliSense: identifier "node" is undefined    c:\Users\Evan\Documents\Visual Studio 2012\Projects\huffman\huffman\Source.cpp  29  12  huffman
9   IntelliSense: identifier "Huffmantree" is undefined c:\Users\Evan\Documents\Visual Studio 2012\Projects\huffman\huffman\Source.cpp  42  10  huffman

Ошибка 5 ошибка C2447: '{': отсутствует заголовок функции (формальный список старого стиля?) C: \ users \ evan \ Documents\visual studio 2012\projects\huffman\huffman\source.cpp 11 1 huffman Ошибка 2 Ошибка C2146: Синтаксическая ошибка: отсутствует ')' перед идентификатором 'root' c: \ users \ evan \ Documents\visual studio 2012\projects\huffman\huffman\source.cpp 10 1 huffman Ошибка 4 Ошибка C2143: синтаксическая ошибка: отсутствует ';' before '{' c:\users\evan\ Documents\visual studio 2012\projects\huffman\huffman\source.cpp 11 1 huffman Ошибка 1 ошибка C2065: 'NodePtr': необъявленный идентификатор c: \ users \ evan \ Documents\visual studio 2012\projects\huffman\huffman\source.cpp 10 1 huffman Ошибка 6 ошибка C2065: 'Huffmantree': необъявленный идентификатор c: \ users \ evan \ Documents\visual studio 2012\projects\huffman\huffman\source.cpp 42 1 huffman Ошибка 3 ошибка C2059: синтаксическая ошибка: ')' c:\users\evan\ Documents\visual studio 2012\projects\huffman\huffman\source.cpp 10 1 huffman

Источник
Другие вопросы по тегам