题目描述
我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。
FBI树是一种二叉树，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2^N
的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：
T的根结点为R，其类型与串S的类型相同；
若串S的长度大于1，将串S从中间分开，分为等长的左右子串S_1
和S_2 ；由左子串S_1构造R的左子树T_1，由右子串S_2构造R的右子树T_2。
现在给定一个长度为2^N的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历序列。
输入格式
第一行是一个整数N(0≤N≤10)，
第二行是一个长度为2^N的“01”串。
输出格式
一个字符串，即FBI树的后序遍历序列。
输入输出样例
输入 #1
3
10001011
输出 #1
IBFBBBFIBFIIIFF
说明/提示
对于40%的数据，N≤2；
对于全部的数据，N≤10。
noip2004普及组第3题
这道题是二叉树的题中比较有意思的一道，难度不大。从FBI这个充满杀气的名字里就能看出它有多么的霸(搞)气(笑)。
楼上把各种建树、遍历的方法都说得很详细了。这里我主要讲一讲结构体、“枚举类型（enum）”和string的子串的使用。代码可能稍微冗长，但是思路非常清晰，非常适合初学者。
拿样例数据来说，图片如下：
这里我采用了从上到下从左向右编号，假设输入的第一个参数为n，可以发现：
1.编号在闭区间
的结点都是叶结点，没有左右子结点。
2.编号在半开半闭区间
的结点是非子结点，第i个结点（i在上述范围内）的左、右孩子编号为
3.没有只有一个孩子的结点。
这是所有满二叉树的共同性质。这两个性质非常重要，一会要用到。
我的思路是，首先构建一个结构体，用来存储树上每个结点。这里，我的上面说的“枚举类型（enum）”就派上用场了。
枚举类型（又叫枚举变量）是一种数据类型，在C++中对应关键字enum。它用来表示一些具有同样性质的变量的集合体。和数组略有不同，枚举类型更像是一种符号。它的声明方式为：
enum agent{Vanguard,Sniper,Guard,Caster,Defender,Medic,Specialist,Supporter};
有人能看出来这是什么吗，有惊喜的
其中列举了几个变量，它们具有各自的值。一般来说，第一个变量的值是0，后面的递增。你也可以指定每个变量的值：
enum agent{Vanguard=1,Sniper,Guard,Caster,Defender,Medic,Specialist,Supporter};
这样第一个元素的值是1，后面的递增。
声明一个枚举类型的变量：
enum agent{Vanguard,Sniper,Guard,Caster,Defender,Medic,Specialist,Supporter};
int main()
{
agent Amiya=Caster;
cout<<Amiya;
}
输出为3。因为对于上述枚举类型，第一个元素是0，后面每个递增（是前一个的数值+1），可以得出Caster的值是3。
enum还有很多其他的用法。关于更多细节可以查看->某不知名官网关于enum的介绍
其实是我懒得
对于这个题，每个结点就是有F、B、I三种状态，用枚举类型再好不过了。不过要注意，直接输出枚举变量会输出数字，需要用switch转为字符。
enum type{F=1,B,I};
然后构建结构体：
struct node
{
type t//枚举类型;
int left//左儿子编号;
int right//右儿子编号;
//对于叶结点，它们的值都是0。这也是在递归遍历时停止的条件。
void node_init(string s)//用字符串初始化每个结点的属性
{
bool have1=false,have0=false;
for(int i=0;i<s.length();i++)//按照题意
{
if(s[i]=='0') have0=true;
if(s[i]=='1') have1=true;
}
if(have0==true&&have1==false) t=B;
else if(have0==false&&have1==true) t=I;
else t=F;//上面三行，type型枚举变量被赋值。
}
}a[2050];//题目中限定n<=10,加上根节点的一层就是11层，共有2048个结点。
我们还需要一个函数来初始化各个结点的儿子情况，赋值规则上面已经提到：
int n;
void init()
{
for(int i=1;i<(int)pow(2,n);i++)
{
a[i].left=i*2;
a[i].right=i*2+1;
}
for(int i=(int)pow(2,n);i<=pow(2,n+1);i++)
{
a[i].left=a[i].right=0;
}
}
然后是递归地使用一个字符串和一个结点的编号来设定每个结点的FBI值。递归到叶节点时直接返回，表示当前递归道路搜索完毕：
void make_tree(string s,int code)
{
if(code!=0)//如果一个结点是叶结点，那么它的孩子编号都是0，初始化时就能体现这一点。
{
a[code].node_init(s);//用当前字符串初始化
make_tree(s.substr(0,s.length()/2),a[code].left);//截取左半部分
make_tree(s.substr(s.length()/2,s.length()/2),a[code].right);//截取右半部分
}
}
这里的substr函数是string的特有函数。用来截取一个string对象里的某一段。用法：
substr(<开始截取的字符串开头下标>,<截取字符串的长度>);
例如:
string s="012345";
cout<<string.substr(0,3);//从0开始，截取长度为3的字符串
输出：012
它可以轻松的分割一个串，比char字符串好多了！
最后是愉快的后序遍历。就像刚才强调的那样，要使用switch来对应地输出字符，而不是直接输出变量：
void back(int code)
{
if(code!=0)
{
back(a[code].left);
back(a[code].right);
switch(a[code].t)
{
case F://也可以是case 1
cout<<"F";
break;
case B:
cout<<"B";
break;
case I:
cout<<"I";
break;
}
}
}
最后，愉快地写主程序，完美地AC!
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>//pow（幂）函数，调用数学库
using namespace std;
enum type{F=1,B,I};
struct node
{
type t;
int left;
int right;
void node_init(string s)
{
bool have1=false,have0=false;
for(int i=0;i<s.length();i++)
{
if(s[i]=='0') have0=true;
if(s[i]=='1') have1=true;
}
if(have0==true&&have1==false) t=B;
else if(have0==false&&have1==true) t=I;
else t=F;
}
}a[2050];
int n;
void init()
{
for(int i=1;i<(int)pow(2,n);i++)
{
a[i].left=i*2;
a[i].right=i*2+1;
}
for(int i=(int)pow(2,n);i<=pow(2,n+1);i++)
{
a[i].left=a[i].right=0;
}
}
void make_tree(string s,int code)
{
if(code!=0)
{
a[code].node_init(s);
make_tree(s.substr(0,s.length()/2),a[code].left);
make_tree(s.substr(s.length()/2,s.length()/2),a[code].right);
}
}
void back(int code)
{
if(code!=0)
{
back(a[code].left);
back(a[code].right);
switch(a[code].t)
{
case F:
cout<<"F";
break;
case B:
cout<<"B";
break;
case I:
cout<<"I";
break;
}
}
}
string m;
int main()
{
cin>>n;
cin>>m;
init();
make_tree(m,1);
back(1);
return 0;
}