题目描述
我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。
FBI树是一种二叉树，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2^N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：
1) T的根结点为R，其类型与串S的类型相同；
2) 若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。
现在给定一个长度为2^N的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历序列。
输入输出格式
输入格式：
第一行是一个整数N（0 <= N <= 10），第二行是一个长度为2^N的“01”串。
输出格式：
包括一行，这一行只包含一个字符串，即FBI树的后序遍历序列。
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
bool x[2000];
int y[5000],a,b,c,d,e,f,g,m,n,k,cnt,bnt,dnt,mmp;
char z,z1[20];
int cot(int p)
{
if(y[p]==3)
{
cout<<"F";
}
if(y[p]==2)
{
cout<<"I";
}
if(y[p]==1)
{
cout<<"B";
}
}
int print(int l)
{
if(mmp==g)
{
return 0;
}
if(y[l*2]==0)
{
cot(l);
mmp++;
y[l]=0;
if(l%2==0)
{
print(l+1);
}
else
{
print(l/2);
}
}
else
{
print(l*2);
}
}
int main()
{
cin>>m;
n=1;
k=1;
for(a=1;a<=m;a++)
{
n=n*2;
k=k+n;
}
g=k;
f=n;
for(a=1;a<=n;a++)
{
cin>>z;
if(z=='0')
{
x[a]=0;
}
else
{
x[a]=1;
}
} // for(a=1;a<=n;a++)
// {
// cout<<x[a];
// }
for(a=1;a<=n;a++)
{
if(x[a]==1)
{
cnt=1;
}
else
{
bnt=1;
}
} if(cnt==1&&bnt==1)
{
y[1]=3;
}
else
{
if(cnt==1)
{
for(a=1;a<=k;a++)
{
cout<<"I";
}
return 0;
}
if(bnt==1)
{
for(a=1;a<=k;a++)
{
cout<<"B";
}
return 0;
}
}
cnt=0;
bnt=0;
dnt++; // g=n;
for(a=1;a<=m;a++)
{
n=n/2;
k=f/n;
for(b=1;b<=k;b++)
{
for(c=(b-1)*n+1;c<=n*b;c++)
{
if(x[c]==1)
{
cnt=1;
}
else
{
bnt=1;
}
}
dnt++;
if(cnt==1&&bnt==1)
{
y[dnt]=3;
}
else
{
if(cnt==1)
{
y[dnt]=2;
}
if(bnt==1)
{
y[dnt]=1;
}
}
cnt=0;
bnt=0;
}
} n=f/2;
print(n);
return 0;
// gets(z1);
// for(a=1;a<=g;a++)
// {
// if(y[a]==3)
// {
// cout<<"F";
// }
// if(y[a]==2)
// {
// cout<<"I";
// }
// if(y[a]==1)
// {
// cout<<"B";
// }
// }
// system("pause");
return 0; }