【NOIP普及组】 FBI树

💐The Begin💐点点关注，收藏不迷路💐

我们可以把由“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]序列。

输入

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

输出

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

样例输入

3
10001011

样例输出

IBFBBBFIBFIIIFF

C语言版本

#include <stdio.h>
#include <string.h>// 判断字符串是否全为指定字符
int isAllSame(char *str, char ch) {int i;int len = strlen(str);for (i = 0; i < len; i++) {if (str[i]!= ch) {return 0;}}return 1;
}// 计算FBI类型
char fbi(char *str) {int len = strlen(str);// 如果字符串长度大于1，递归处理子串if (len > 1) {char leftStr[len / 2 + 1];char rightStr[len - len / 2 + 1];strncpy(leftStr, str, len / 2);leftStr[len / 2] = '\0';strncpy(rightStr, str + len / 2, len - len / 2);rightStr[len - len / 2] = '\0';printf("%c", fbi(leftStr));printf("%c", fbi(rightStr));}// 判断字符串是否全为0if (isAllSame(str, '0')) {return 'B';}// 判断字符串是否全为1else if (isAllSame(str, '1')) {return 'I';}return 'F';
}int main() {int n; // n：输入的整数N，表示后续输入字符串的长度相关信息scanf("%d", &n);char s[1024]; // s：存储输入的字符串scanf("%s", s);printf("%c", fbi(s));return 0;
}

C++ 版本

#include <iostream>
#include <string>// 判断字符串是否全为指定字符
bool isAllSame(const std::string &str, char ch) {for (char c : str) {if (c!= ch) {return false;}}return true;
}// 计算FBI类型
char fbi(const std::string &str) {int len = str.length();// 如果字符串长度大于1，递归处理子串if (len > 1) {std::string leftStr = str.substr(0, len / 2);std::string rightStr = str.substr(len / 2);std::cout << fbi(leftStr);std::cout << fbi(rightStr);}// 判断字符串是否全为0if (isAllSame(str, '0')) {return 'B';}// 判断字符串是否全为1else if (isAllSame(str, '1')) {return 'I';}return 'F';
}int main() {int n; // n：输入的整数N，表示后续输入字符串的长度相关信息std::cin >> n;std::string s; // s：存储输入的字符串std::cin >> s;std::cout << fbi(s) << std::endl;return 0;
}

Java版本

import java.util.Scanner;class Main {// 判断字符串是否全为指定字符static boolean isAllSame(String str, char ch) {// 遍历字符串中的每个字符for (int i = 0; i < str.length(); i++) {// 如果有任何一个字符与指定字符不同，返回falseif (str.charAt(i)!= ch) {return false;}}// 如果所有字符都与指定字符相同，返回truereturn true;}// 计算FBI类型static char fbi(String str) {int len = str.length();// 如果字符串长度大于1，递归处理子串if (len > 1) {String leftStr = str.substring(0, len / 2);String rightStr = str.substring(len / 2);// 先递归处理左子串并输出结果System.out.print(fbi(leftStr));// 再递归处理右子串并输出结果System.out.print(fbi(rightStr));}// 判断字符串是否全为0if (isAllSame(str, '0')) {return 'B';}// 判断字符串是否全为1else if (isAllSame(str, '1')) {return 'I';}return 'F';}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n; // n：输入的整数N，表示后续输入字符串的长度相关信息n = scanner.nextInt();String s = scanner.next(); // s：存储输入的字符串System.out.println(fbi(s));// 关闭Scanner，释放资源scanner.close();}
}

Python版本

#  Python 3 风格的 print 函数
from __future__ import print_functiondef fbi(s):length = len(s)# 如果字符串长度大于1，递归处理子串if length > 1:left_str = s[:length // 2]right_str = s[length // 2:]print(fbi(left_str), end='')print(fbi(right_str), end='')# 判断字符串是否全为0if all(char == '0' for char in s):return 'B'# 判断字符串是否全为1elif all(char == '1' for char in s):return 'I'return 'F'n = int(input())  # n：输入的整数N，表示后续输入字符串的长度相关信息
s = input()  # s：存储输入的字符串print(fbi(s), end='')

💐The End💐点点关注，收藏不迷路💐