题意:

输入一个01串,为s

将s分两半 , 一个为l , 一个为r

如果l==r,0返回"B",1返回"I"

如果l与r全为0就说明s的节点为"B"

如果l与r全为1就说明s的节点为"I"

如果l与r有1有0就说明s的节点为"F"

判断完后,再递归l和r(重复以上操作,直到l和r重合,在判断是"B"还是"I")

最后输出这个树的后序遍历

模拟:

输入 : 10001011

输出 : IBFBBBFIBFIIIFF

模拟过程:
    10001011
   /        \
 1000      1011 --- F
 /  \      /  \
 10 00     10 11 --- F F
/ \ / \   / \ / \
1 0 0 0   1 0 1 1 --- F B F I
| | | |   | | | |
1 0 0 0   1 0 1 1 --- I B B B I B I I
所构成的树:
       F
      / \
     F   F
    / \ / \
   F  B F  I
 //  /| |\  \\
I B B B I B I I
后序遍历:
IBFBBBFIBFIIIFF

代码:

#include<iostream>
using namespace std;
string s;//01串
void f(int l,int r)
{
	if(l==r)//为一个数字时
	{
		if(s[l]=='0')//判断是0还是1
		{
			cout<<'B';
		}
		else
		{
			cout<<'I';
		}
		return;//返回
	}
	int m=l+(r-l)/2;//l , r 的中间
	f(l,m);//左边
	f(m+1,r);//右边
	bool f1=false,f2=false;//标记是否出现过0,1
	for(int i=l;i<=r;i++)
	{
		if(s[i]=='0')//出现过0
		{
			f1=true;
		}
		if(s[i]=='1')//出现过1
		{
			f2=true;
		}
	}
	if(f1 && f2)//有0也有1时
	{
		cout<<'F';
	}
	else if(f1 && (!f2))//全0时
	{
		cout<<'B';
	}
	else
	{
		cout<<'I';//全1时
	}
}
int main()
{
	int n;//其实n根本没有用
	cin>>n;//输入
	cin>>s;//输入
	f(0,s.size()-1);//FBI树
	return 0;//完结散花
}