洛谷P1087.FBI树 （题目 + 代码 + 详细注释）

我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。
FBI树是一种二叉树1，它的结点类型也包括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树，并输出它的后序遍历2序列。

输入格式:

输入的第一行是一个整数N(0<=N<=10)，第二行是一个长度为2^N的“01”串。

输出格式:

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

提示:

NOIP2004普及组第三题

限制:

每个测试点1s

样例 1 :

输入:
3
10001011

输出:
IBFBBBFIBFIIIFF

样例 2 :

输入:
0
0

输出:
B

//题意及思路：就是建立一颗二叉树，然后输出后续遍历的结果；唯一特殊的是，建立二叉树的规则：把父结点的字符串等分两份，分别给其左右儿子，递归执行上述过程，直到父结点的字符串不能二分为止

以下是我根据样例手动建的一颗二叉树

代码：

#include
using namespace std;
const int N = 105;
const int INF = 0x3fffffff;
typedef long long ll;struct node {         //每个结点的结构体char id;string ss;node* lc, *rc;
};char getid(string s) {          //判断字符串的类型（用string类的find函数很方便）if (s.find('0') == s.npos) return 'I';else if (s.find('1') == s.npos) return 'B';return 'F';
}void gettree(node*& root) {            //建树（注意是指针的引用）if (root->ss.size() > 1) {            //字符串能二分node *temp = new node;            //分给左儿子的部分temp->ss = root->ss.substr(0, root->ss.size() / 2);temp->id = getid(temp->ss);temp->lc = temp->rc = NULL;root->lc = temp;temp = new node;                  //分给右儿子的部分temp->ss = root->ss.substr(root->ss.size() / 2, root->ss.size() / 2);temp->id = getid(temp->ss);temp->lc = temp->rc = NULL;root->rc = temp;gettree(root->lc);               //递归建树gettree(root->rc);}
}void postravel(node* &root) {             //后序遍历if (!root) return;postravel(root->lc);postravel(root->rc);cout << root->id;                //输出每个结点的id
} int main() {int n;string s;cin >> n >> s;node* root = new node;               //初始化树的根节点root->id = getid(s);root->ss = s;root->lc = root->rc = NULL;         gettree(root);                  //以root为根结点建树postravel(root);                   //以root为根结点后序遍历return 0;
}

//另一种解法：还可以根据二叉树的性质：如果父节点的下标是k,则其左儿子的下标是2 * k, 右儿子的下标是2 * k + 1；利用这个性质，可以建一个数组，储存每个结点的字符串类型，然后输出即可。在此就不上代码了，有兴趣的读者可自行实现 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！