• 欢迎光临~

二叉树遍历-FBI树

开发技术 开发技术 2022-06-11 次浏览

[NOIP2004 普及组] 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)从中间分开,分为等长的左右子串(S_1)(S_2);由左子串(S_1)构造R的左子树(T_1),由右子串(S_2)构造(R)的右子树(T_2)

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

3
10001011

样例输出 #1

IBFBBBFIBFIIIFF

提示

对于40%的数据,(N le 2)

对于全部的数据,(N le 10)

思路

后序遍历,先递归左子树右子树再处理中间节点,判断该子树是哪种类型。

代码

#include<iostream>
using namespace std;
string s;
int n;
char pd(int l, int r) {
	int num0 = 0, num1 = 0;
	for (int i = l; i <= r; i++) {
		if (s[i] == '0')num0++;
		if (s[i] == '1')num1++;
	}
	if (num0 == 0)return 'I';
	if (num1 == 0)return 'B';
	if (num0 && num1)return 'F';

}
void dfs(int l,int r) {
	int mid = (l + r ) / 2;
	if (l != r) {
		dfs(l, mid);
		dfs(mid + 1, r);
	}
	cout << pd(l, r);
}
int main() {
	cin >> n >> s;
	int l = s.size()-1;
	dfs(0,l);
}
程序员灯塔
转载请注明原文链接:二叉树遍历-FBI树
喜欢 (0)