[题解]FBI树(fbi)

啊哈磊

输入数据：

3
10001011

输出数据：
IBFBBBFIBFIIIFF

代码：

[code=Cpp width=740px]#include <stdio.h>
#include <math.h>
char a[2001]={'\0'},b[2001]={'\0'};
int n;
void dfs(int i)
{
    //如果是叶节点(就是最后一层的节点)就输出
    if( i>=(int)pow(2,n-1) && i<=(int)pow(2,n)-1 )
    {
        printf("%c",b);
        return;//千万不要忘记
    }
    dfs(i*2);//先左孩子
    dfs(i*2+1);//再右孩子
    printf("%c",b);//最后是父亲
    return;//这个return可以省略
}

int main()
{
    int i,t,k,left,right;
    scanf("%d",&t);
    scanf("%s",a);
    //n表示这棵树一共有多少层
    n=t+1;
    k=n;
    left=(int)pow(2,k-1);
    right=(int)pow(2,k)-1;
    //先将读入的'0'和'1'转化正'I'和'F',并放在B数组(用来存放这棵树)中的对应位置
    //left是最后一层的最左边，right表示最后一层的最右边
    for(i=left;i<=right;i++)
    {
        if(a[i-left]=='1')
            b='I';
        else
            b='B';
    }
   
    k--;//最后一层处理完了，再处理上一层
    //求这个树上一层的左右边界
    left=(int)pow(2,k-1);
    right=(int)pow(2,k)-1;
    //当不是根节点的时候循环，根节点有个特点 2^(1-1)==2^1-1
    while(left!=right)
    {
        for(i=left;i<=right;i++)
        {
            //再用一位数组存放一个完全二叉树或者满二叉树时
            //如果父亲的节点编号是i,那么左孩子的编号是2*i,右孩子的编号是2*i+1
            if(b[i*2]==b[i*2+1])//如果他的左右孩子是一样的,就随便选一个给父亲
                b=b[i*2];
            else//如果不一样就是赋值'F'
                b='F';
        }
        //当前这层处理完后，再求上一层
        k--;
        left=(int)pow(2,k-1);
        right=(int)pow(2,k)-1;
    }
    //第一层根节点单独处理
    if(b[2]==b[3])
        b[1]=b[2];
    else
        b[1]='F';
        
    //开始进行后序遍历，从根节点开始
    dfs(1);
        
    getchar();
    getchar();
    return 0;
}
</math.h></stdio.h>[/code]