WIKIOI-1094 FBI树(未完成)

1094 FBI树
题目描述 Description
我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。

FBI树是一种二叉树[1]，它的结点类型也包括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树，并输出它的后序遍历[2]序列。

输入描述 Input Description
输入的第一行是一个整数N（0 <= N <= 10），第二行是一个长度为2^N的“01”串。

输出描述 Output Description
输出t包括一行，这一行只包含一个字符串，即FBI树的后序遍历序列。

样例输入 Sample Input
3

10001011

样例输出 Sample Output
IBFBBBFIBFIIIFF

数据范围及提示 Data Size & Hint
对于40%的数据，N <= 2；

对于全部的数据，N <= 10。

不知道为什么WA，所有数据都能通过.....有空回来继续解决
思路是对的

#include<stdio.h>
#include<string.h>
#include<math.h>
char a[3000];
struct node
{
   char flag;
   int L;
   int R;
}b[10000];
int n,m,k,x=0;
char Sure(int x,int m)//确定子串类型
{
    //printf("@1\n");
    int i,f1=0,f2=0;
    if(x==m)
    {
       if(a[x]=='1')
       return 'I';
       else
       return 'B';
    }
    else
    {
        for(i=x;i<=m;i++)
        {
           if(a[i]=='0') f1=1;
           else
           if(a[i]=='1') f2=1;
        }
        if(f1==1&&f2==1)
        return 'F';
        else if(f1==0&&f2==1)
        return 'I';
        else
        return 'B';
    }
}
void BuildTree(int k,int x,int m)//建立二叉树
{
    //printf("@2 x=%d m=%d\n",x,m);
    b[k].flag=Sure(x,m);
    if(m==x)
    return;
    else
    {
       b[k].L=2*k;
       BuildTree(2*k,x,(m+x)/2);
       b[k].R=2*k+1;
       BuildTree(2*k+1,(m+x)/2+1,m);
    }
}
void Ergodic(int u)//后续遍历二叉树
{
   //printf("@3\n");
   if(b[u].L!=0)
   Ergodic(b[u].L);
   if(b[u].R!=0)
   Ergodic(b[u].R);
   printf("%c",b[u].flag);
}
int main()
{
    int i,v1=0,v2=0;
    scanf("%d",&n);
    memset(b,0,sizeof(b));//清零
    m=(int)pow(2,n);
    getchar();
    for(i=1;i<=m;i++)
    scanf("%c",&a[i]);
    k=1;
    BuildTree(k,1,m);
    Ergodic(1);
    printf("\n");
    return 0;
}