【蓝桥】FBI树

题目

题目描述

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

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

  1. T 的根结点为 R,其类型与串 S 的类型相同;
  2. 若串 S 的长度大于 1,将串 S 从中间分开,分为等长的左右子串 S1 和 S2 ;由左子串 S1 构造 R 的左子树 T1,由右子串 S2 构造 R 的右子树 T2。

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

输入描述

第一行是一个整数 N(0≤N≤10)。

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

输出描述

输出一个字符串,即 FBI 树的后序遍历序列。

输入输出样例

示例

输入

1
2
3
10001011

输出

1
IBFBBBFIBFIIIFF

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 128M

解题

源码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstring>
using namespace std;
char s[2000], tree[280000];

void buildTree(int k, int left, int right)
{
if (left == right)
{
if (s[right] == '1')
tree[k] = 'I';
else
tree[k] = 'B';
return;
}
int mid = (left + right) / 2; //分成两半
buildTree(2 * k, left, mid); //递归左半
buildTree(2 * k + 1, mid + 1, right); //递归右半

if (tree[2 * k] == 'B' && tree[2 * k + 1] == 'B') //左右儿子都是B
tree[k] = 'B';
else if (tree[2 * k] == 'I' && tree[2 * k + 1] == 'I') //左右儿子都是I
tree[k] = 'I';
else
tree[k] = 'F';
}

void postorder(int v)
{ //后序遍历
if (tree[2 * v])
postorder(2 * v);
if (tree[2 * v + 1])
postorder(2 * v + 1);
printf("%c", tree[v]);
}

int main()
{
int n;
scanf("%d", &n);
scanf("%s", s + 1);
buildTree(1, 1, strlen(s + 1));
postorder(1);
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#下面的代码是罗勇军老师补充的python代码
def build_FBI(k,left,right):
if left==right:
if s[right]=='1': tree[k]='I'
else: tree[k]='B'
return
mid=(left+right)//2
build_FBI(2*k,left,mid)
build_FBI(2*k+1,mid+1,right)

if tree[2*k]=='B' and tree[2*k+1]=='B': tree[k]='B'
elif tree[2*k] == 'I' and tree[2*k+1]=='I': tree[k]='I'
else: tree[k]='F'

def postorder(v):
if tree[2*v] != '': postorder(2*v)
if tree[2*v+1] != '': postorder(2*v+1)
print(tree[v],end='')


n=int(input())
s=input()
tree=['']*1000000

build_FBI(1,0, len(s)-1)
postorder(1)

总结

C++版

  1. 值得注意的点是tree中单数是左子树,双数是右子树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//二叉树数据结构
struct Node{ //静态二叉树
char value;
int lson, rson; //左右孩子,编码时把lson简写为ls或者l
}tree[N]; //编码时把tree简写为t

//先序遍历
void preorder (node *root){
cout << root ->value; //输出
preorder (root -> lson); //递归左子树
preorder (root -> rson); //递归右子树
}

//中序遍历
void inorder (node *root){
inorder (root -> lson); //递归左子树
cout << root ->value; //输出
inorder (root -> rson); //递归右子树
}

//后序遍历
void postorder (node *root){
postorder (root -> lson); //递归左子树
postorder (root -> rson); //递归右子树
cout << root ->value; //输出
}

Python版

  1. 一样一样的