冲刺阶段：霍夫曼树查找

这个题目是看到别人说的，也没有oj判断，题目大概是这个意思： 比如

2 ：111

1 ：0

3: 110

构造哈夫曼树，给你一串编码 比如 1111100 让你找出编码所代表的原文，然后再输出哈夫曼树中每一个结点被访问的次数。 先上一波，我一开始写的比较蠢的代码，虽然结果一样，如下：忽略了只有叶子节点才有数据的性质

#include
#include
#include
using namespace std ;
struct Node{
Node *left ;
Node *right;
char value ;
bool flag ;
Node(){
left = NULL;
right= NULL ;
flag = false ;
}
}*root;
char Search(Node *root,string target)
{
Node *p = root;
for(int i = 0 ; i {
if(target[i]=='0')
{
if(p->left)
{
p=p->left;
}else {
return '-' ;
}
}else if(target[i]=='1'){
if(p->right)
{
p=p->right;
}else {
return '-' ;
}
}
}
if(p->flag)
return p->value;
else
return '-';
}
bool flag ;
void dfs(Node *root,string deal,string res)
{
if(deal=="")
{
flag =true ;
cout < }
for(int i = 1 ; i <= deal.size();i++)
{
char res_char= Search(root,deal.substr(0,i));
if(res_char !='-')
{
dfs(root,deal.substr(i,deal.size()-i),res+res_char);
if(flag)
return ;
}
}
}
int main(){
int num ;
string deal;
char c_from ;
string res ;
while(cin>>deal)
{
root = new Node();
scanf("%d",&num);
while(num--)
{
Node *p = root;
cin>>c_from >> res ;
for(int i = 0 ; i {
if(res[i]=='0')
{
if(p->left==NULL)
p->left = new Node();
p=p->left;
}else
{
if(p->right==NULL)
p->right = new Node();
p=p->right;
}
}
p->flag = true ;
p->value = c_from;
}
flag = false ;
dfs(root,deal,"");
}
}


经过更改后，代码如下，还可以方便的记录访问次数

#include
#include
#include
using namespace std ;
struct Node{
Node *left ;
Node *right;
char value ;
int Count ;
bool flag ;
Node(){
left = NULL;
right= NULL ;
flag = false ;
Count = 0 ;
}
}*root;
string Search(Node *root,string target)
{
string res ="";
Node *p = root;
for(int i = 0 ; i {
if(target[i]=='0')
{
if(p->left)
{
p=p->left;
}
}else if(target[i]=='1'){
if(p->right)
{
p=p->right;
}
}
if(p->flag)
{
res += p->value;
p=root;
}
}
return res ;
}
int main(){
int num ;
string deal;
char c_from ;
string res ;
while(cin>>deal)
{
root = new Node();
scanf("%d",&num);
while(num--)
{
Node *p = root;
cin>>c_from >> res ;
for(int i = 0 ; i {
if(res[i]=='0')
{
if(p->left==NULL)
{
p->Count ++ ;
p->left = new Node();
}
p=p->left;
}else
{
if(p->right==NULL)
{
p->Count ++ ;
p->right = new Node();
}
p=p->right;
}
}
p->flag = true ;
p->value = c_from;
}
cout < }
}