添加上解码。

解码要求：

　　根据输入的01字符串输出相对应的字符。

解码过程：

（1）node *p,p作为移动指针，在已经构造好的哈夫曼树中进行移动。移动规则，遇到0向左子树移动，遇到1向右子树移动。

（2）输入01字符串s（可以用string也可以用char数组，在此使用string），求出串的长度s.size().

（3）进入循环,进行相应判断以及输出。关键代码：

for(int i=0;i
     
      lchild!=NULL)            {                p=p->lchild;            }        }        else if(s[i]=='1')        {            if(p->rchild!=NULL)            {                p=p->rchild;            }        }        if(p->lchild==NULL&&p->rchild==NULL)        {            printf("%c",p->ch);            p=tree;        }
     

给出全部代码以及运行实例：

1 #include 
      
         2 #define max_size 10010  3 char c[max_size];  4 double f[max_size];  5   6 using namespace std;  7 typedef struct node  8 {  9     char ch; 10     double freq; 11     node *lchild; 12     node *rchild; 13     node(char c=0,double f=0,node *l=NULL,node *r=NULL): 14         ch(c),freq(f),lchild(l),rchild(r) {} 15 }; 16 typedef struct cmp 17 { 18     bool operator()(node*&a,node*&b) 19     { 20         return a->freq>b->freq; 21     } 22 }; 23 node* createTree(int n) 24 { 25     priority_queue
       
        
         ,cmp>que; 26     for(int i=1; i<=n; i++) 27     { 28         cin>>c[i]>>f[i]; 29         que.push(new node(c[i],f[i])); 30     } 31     while(que.size()>1) 32     { 33         node *l=que.top(); 34         que.pop(); 35         node *r=que.top(); 36         que.pop(); 37         node *newnode=new node(0,l->freq+r->freq,l,r); 38         que.push(newnode); 39     } 40     return que.top(); 41 } 42  43 void decode(string s,node *tree) 44 { 45     node *p=tree; 46     cin>>s; 47     getchar(); 48     int lens=s.size(); 49     for(int i=0;i
         
          lchild!=NULL) 54             { 55                 p=p->lchild; 56             } 57         } 58         else if(s[i]=='1') 59         { 60             if(p->rchild!=NULL) 61             { 62                 p=p->rchild; 63             } 64         } 65         if(p->lchild==NULL&&p->rchild==NULL) 66         { 67             printf("%c",p->ch); 68             p=tree; 69         } 70     } 71     printf("\n"); 72 } 73  74 void printInfo(const node *tree,string code) 75 { 76     if(tree->lchild==NULL&&tree->rchild==NULL) 77     { 78         cout<
          
           ch<<":"<
           <<" "; 79 return; 80 } 81 if(tree->lchild!=NULL)printInfo(tree->lchild,code+'0'); 82 if(tree->rchild!=NULL)printInfo(tree->rchild,code+'1'); 83 } 84 85 void deleteTree(node *tree) 86 { 87 if(tree->lchild!=NULL)deleteTree(tree->lchild); 88 if(tree->rchild!=NULL)deleteTree(tree->rchild); 89 delete(tree); 90 } 91 92 int main() 93 { 94 int n; 95 string s; 96 priority_queue
            
             
              ,greater
              
                >que; 97 while(~scanf("%d",&n)) 98 { 99 node *tree=createTree(n);100 printf("Huffman code:\n");101 printInfo(tree,"");102 printf("\n");103 decode(s,tree);104 deleteTree(tree);105 }106 }
              
             
            
          
         
        
       
      

 

输入：

首先输入要构造的哈夫曼树有多少的元素。

然后输入每个元素以及其出现的频率（上面全部设为1）

然后输入01串，对其按照上面哈夫曼树的规则进行解码。