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