[数据结构与算法]洛谷P1087 FBI树

题目

添加链接描述

思路

其实这个树很简单，就是一个满二叉树，我们利用父亲结点是i左结点是2* i右节点是2*i+1来存储。就与data信息是字符串所以我利用了一个结构体Node来存储相应信息。存储之后还要对剩余的叶子结点进行处理，就是将叶子结点作为data存入结构体中，便于写递归。

AC代码

#include <bits/stdc++.h>
using namespace std;

struct Node {
	string left, right, data;
} I[3000];

void creat_tree(string s, int node) {
	if (s.size() == 1)
		return;
	I[node].data = s;
	I[node].left = s.substr(0, s.size() / 2);
	creat_tree(I[node].left, node * 2);
	I[node].right = s.substr(s.size() / 2);
	creat_tree(I[node].right, node * 2 + 1);
}

string res(string s) {
	if (s.find("0") == -1)
		return "I";
	else if (s.find("1") == -1)
		return "B";
	else
		return "F";
}

void dfs(int start, int end) {
	if ((I[start].data).size() != 1) {
		dfs(2 * start, 2 * start + (end - start) / 2);
		dfs(2 * start + 1, 2 * start + 1 + (end - start) / 2);
	}
	cout << res(I[start].data);
}

int main() {
	int N;
	cin >> N;
	string s;
	cin >> s;
	if (N == 0) {
		cout << res(s);
		return 0;
	}
	creat_tree(s, 1);
	int root = pow(2, N);
	for (int i = 1; i < root; ++i) {
		if ((I[i].data).size() == 2) {
			I[2 * i].data = I[i].left;
			I[2 * i + 1].data = I[i].right;
		}
	}
	dfs(1, root);
}

后言

泪目啊家人们，一个多月终于对递归开了点窍！！！！