哈夫曼樹及解碼，
添加上解碼。
解碼要求：
根據輸入的01字符串輸出相對應的字符。
解碼過程：
（1）node *p,p作為移動指針，在已經構造好的哈夫曼樹中進行移動。移動規則，遇到0向左子樹移動，遇到1向右子樹移動。
（2）輸入01字符串s（可以用string也可以用char數組，在此使用string），求出串的長度s.size().
（3）進入循環,進行相應判斷以及輸出。關鍵代碼：
for(int i=0;i<lens;i++)
{
if(s[i]=='0')
{
if(p->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 <bits/stdc++.h>
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<node*,vector<node*>,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<lens;i++)
50 {
51 if(s[i]=='0')
52 {
53 if(p->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<<tree->ch<<":"<<code<<" ";
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<node*,vector<node*>,greater<node*> >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 }
View Code
輸入：
首先輸入要構造的哈夫曼樹有多少的元素。
然後輸入每個元素以及其出現的頻率（上面全部設為1）
然後輸入01串，對其按照上面哈夫曼樹的規則進行解碼。
