游客 注册 | 登录
中文 | En

2360 - FBI树

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 125 MB

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

<span style="line-height:1.5;">FBI树是一种二叉树（如下图），它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：</span>


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


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

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

题目输入

每组输入数据的第一行是一个整数N（0<=N<=10），第二行是一个长度为2N的“01”串。 


数据规模：<br />

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

<div>
	<br />
</div>

题目输出

每组输出包括一行，这一行只包含一个字符串，即FBI树的后序遍历序列。


输入/输出样例

输入格式

3
10001011

输出格式

IBFBBBFIBFIIIFF

C语言解答

#include <stdio.h>
#include <math.h>
struct list
{
	int left;
	int data;
	char ch;
   int right;
	};
struct list tree[2050];

void print(int root)
{
	if(root!=-1)
	  {
		  print(tree[root].left);
		  print(tree[root].right);
		  printf("%c",tree[root].ch);
		  }
	}
main()
{
	
	int i=1,n;
	//FILE *fin=fopen("fbi.in","r");
	scanf("%d",&n);
	int front,len,node;
	front=pow(2,n);
	len=pow(2,n+1);
	node=pow(2,n-1);
	  
	
	
	for(i=front;i<len;i++)
	 {
		 scanf("%1d",&tree[i].data);
		 tree[i].left=-1;
		 tree[i].right=-1;
		 if(tree[i].data==1)
		   tree[i].ch='I';
		 else
		   tree[i].ch='B';
		 }
		/*for(i=1;i<len;i++)
		 printf("%c ",tree[i].ch);
		 printf("\n");*/
    int temp=n-1;
    while(temp>=0)
      {
	      for(i=pow(2,temp);i<pow(2,temp+1);i++)
	        {
		        tree[i].left=2*i;
		        tree[i].right=2*i+1;
		        if(tree[2*i].ch=='B' && tree[2*i+1].ch=='B')
		        tree[i].ch='B';
		        else if(tree[2*i].ch=='I' && tree[2*i+1].ch=='I')
		        tree[i].ch='I';
		        else tree[i].ch='F';
		        }
	      temp--;
	      }
	   print(1);
	  
	}

C++解答

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int m;
char str[3333];
char put[3] = {'B', 'I' ,'F'};
int dfs(int sx,int ex)
{
    int a,b;
    if(sx==ex)
    {
        printf("%c", put[str[sx] - '0']);
        return str[sx] - '0';
    }
    a=dfs(sx,(sx+ex)/2);
    b=dfs((ex+sx)/2+1,ex);
    if(a == b)
        {
        printf("%c", put[a]);
        return a;
        }
    else
        {
        cout<<'F';
       return 2;
       }
}
int main()
{
    scanf("%d",&m);
    scanf("%s",str);
    dfs(0,strlen(str)-1);
    cout<<endl;
    return 0;
}
请先登陆