NOIP 2004 普及组 复赛 FBI树

NOIP 2004 普及组 复赛 FBI树

1.阅读题目，还有些不知所云。

2.对样例进行手动模拟，弄明白题意了。

10001011

 FBI树如下图所示

F

F     F

F  B  F  I

I B B B I B I I

1) T的根结点为R，其类型与串S的类型相同；此句是核心中的核心，也即F B I三种根节点。

3.接下来编程实现是重点。先建树，子弟相信行一层一层建树，用一维数组存储，第1号(第0号不使用)元素开始使用数组。父k,左子2*k,右子2*k+1。再进行遍历，后序遍历，采用递归的方式。

4.建树函数，遍历函数编写。

5.代码编写完成，提交AC，递归函数写法，记得先写终结条件。

6.此文写得不错，读者也可以借鉴。http://blog.csdn.net/dogeding/article/details/52727239

7.此题，可以借鉴的是：二叉树的存储，二叉树的遍历。

附上AC代码，编译环境Dev-C++4.9.9.2

#include <stdio.h>

int n;

char a[1024+10];

char b[2048+10];

void build(char *s,int n){//建树代码

    //底层构造

    int i,j=0;

    for(i=(1<<n);i<=(1<<(n+1))-1;i++){

        b[i]=a[j++]=='0'?'B':'I';

    }

    //自底向上构造

    for(i=n-1;i>=0;i--)

        for(j=(1<<i);j<=(1<<(i+1))-1;j++)

            if(b[2*j]=='B'&&b[2*j+1]=='B')

                b[j]='B';

            else if(b[2*j]=='I'&&b[2*j+1]=='I')

                b[j]='I';

            else

                b[j]='F';

}

void visit(int node){//后序遍历代码

    if(node>(1<<(n+1))-1)

        return;

    visit(node*2);//左子树

    visit(node*2+1);//右子树

    printf("%c",b[node]);//根

}

int main(){

    scanf("%d",&n);

    scanf("%s",a);

    build(a,n);

    visit(1);

    printf("\n");

    return 0;

}