P1087 FBI树(二叉树+先序遍历构树+后序遍历输出)

时间:2021-10-12 10:01:22

P1087 FBI树(二叉树+先序遍历构树+后序遍历输出)

P1087 FBI树(二叉树+先序遍历构树+后序遍历输出)

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;
}