解碼霍夫曼樹

Question

我正在實現一個函數，它需要一個樹和一個編碼的字符串。 例子：

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

我有麻煩時實施向左或向右不爲空，也就是當我還得繼續到下一個節點會發生什麼。

有什麼建議嗎？

編輯：

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

Answer 1

以下可能會有所幫助：

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

Answer 2

這是最簡單的代碼之一，基本上你需要檢查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; 
     } 
    } 

} 

Answer 3

當我運行這個

#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：\用戶\埃文\文件\的Visual Studio 2012 \項目\霍夫曼\霍夫曼\ source.cpp 11 1 huffman Error 2 error C2146：syntax error：missing'）'before'identifier'root'c：\ users \ evan \ documents \ visual studio 2012 \ projects \ huffman \ huffman \ source.cpp 10 1 huffman 錯誤4錯誤C2143 ：語法錯誤：缺少';'之前'{'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