题目描述

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

FBI树是一种二叉树[1]，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：

1) T的根结点为R，其类型与串S的类型相同；

2) 若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。

现在给定一个长度为2N的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历[2]序列。

[1] 二叉树：二叉树是结点的有限集合，这个集合或为空集，或由一个根结点和两棵不相交的二叉树组成。这两棵不相交的二叉树分别称为这个根结点的左子树和右子树。

[2] 后序遍历：后序遍历是深度优先遍历二叉树的一种方法，它的递归定义是：先后序遍历左子树，再后序遍历右子树，最后访问根。

输入描述: 

		
		

			第一行是一个整数N（0 <= N <= 10）
		


		

			第二行是一个长度为2N的“01”串。

输出描述: 

一个字符串，即FBI树的后序遍历序列。
示例1

输入 

3
10001011

输出 

IBFBBBFIBFIIIFF

备注: 

对于40%的数据，N <= 2；
对于全部的数据，N<= 10。

思路

这其实就是一颗完全二叉树。不要被里面有关归并排序的内容混淆了。先输入的那部分01串就是树的叶子，可以直接构造，构造完之后再从第一个非叶子节点逆序构造这棵树，依据题目的规则，全零(B)则B，全一(I)，同时包含01(F)则F。完全二叉树和堆一样，用数组存储就行了，最后再写个递归的后序遍历就行了。(读入字符吸收换行！！！)

代码 

//FBI树(模拟 完全二叉树) 
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1 << 10 + 10;

int m , maxn;
char a[N] , ch;

void print(int u)
{
	if(u < maxn)
	{
		print(2 * u);
		print(2 * u + 1);
		printf("%c" , a[u]);
	}
}

int main()
{
 	int n;
 	scanf("%d" , &n);
 	getchar();
 	
 	maxn = 1 << (n + 1) , m = 1 << n;
 	for(int i = 0 ; i < m ; i++)
 	{
 		scanf("%c" , &ch);
		a[m + i] = ch == '0' ? 'B' : 'I';
//		cout<<a[m + i]<<endl;	
	}
	
	for(int i = m - 1 ; i ; i--)
	{
		if(a[i * 2] == 'B' && a[i * 2 + 1] == 'B')
			a[i] = 'B';
		else if(a[i * 2] == 'I' && a[i * 2 + 1] == 'I')
			a[i] = 'I';
		else
			a[i] = 'F';
	}
	
//	for(int i = 1 ; i < maxn ; i++)
//		printf("%c" , a[i]);

	print(1);
	return 0; 
}