P1087 FBI树(二叉树+先序遍历构树+后序遍历输出）
#include<cstdio>
#include<iostream>
using namespace std;
//二叉树的元素一定是偶数（废话）
char str[2000];
int n;
void binarytree(int x,int y)
{
int i;
if(y>x) //先序遍历构树 根节点------左子树------右子树，
{
binarytree(x,(x+y)/2);//对于个数是偶数，（x+y)/2得到的结果就是左边界
binarytree((x+y)/2+1,y); //因为是从左边开始构树，所以每次左边的树递归回溯就直接到右边的树了
}
int B=1,I=1;
for(i=0;i<=y-x;i++) //为什么是i<=y-x;因为是取区间内的所有元素。
{
if(str[x+i]=='0') //一定是x+i,因为区间是从左边开始的
I=0;
else if(str[x+i]=='1') //后序遍历输出 左子树------右子树------根节点
B=0;
}
if(B)
cout<<'B';
else if(I)
cout<<'I';
else
cout<<'F';
}
int main()
{
scanf("%d",&n);
getchar();
scanf("%s",str);
binarytree(0,(1<<n)-1);//因为数组是从0开始的，所以也把二叉树的最左的坐标也设为（0,0）
return 0;
}