|
题目描述
我们可以把由“O”和“1”组成的字符串分为三类：全“O”串称为B串，全“1”串称为I串，既含“O”又含“1”的串则称为F串。FBI树是一种二叉树，它的结点类型也包括F结点、B结点和I结点三种。由一个长度为2的N次方的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：
(1)T的根结点为R，其类型与串S的类型相同；
(2)若串S的长度大于1，将串S从中间分开，分为等长的左右子串Sl和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。
现在给定一个长度为2N的“O1”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历序列。
输入
第1行是一个整数N(O≤N≤10)，第2行是一个长度为2N的“01”串。
输出
1行只包含一个字符串，即FBI树的后序遍历序列。
样例输入
3
10001011
样例输出
IBFBBBFIBFIIIFF
可以把输入的值理解为二叉树的‘层数减一’和‘叶子节点’，这个FBI树一定是一个完全二叉树。
#include?<iostream>
#include?<algorithm>
#include?<string>
using?namespace?std;
int?num;//输入二叉树的层数，零为叶子结点
int?step=0;//公共变量，遍历叶子结点的下标
string?ret;//输入的叶子结点
string?tem;//递归返回的后序遍历
char?tree(int?num){
????if(num>0){//如果不是叶子结点时
????????char?a?=?tree(num-1);
????????char?b?=?tree(num-1);
????????char?c;
????????if(a=='F'||b=='F'||a!=b)?c='F';//通过返回值判断树的性质
????????else?c=b;?
????????ret+=c;
????????return?c;
????}
????else{//递归到叶子结点，从字符串中取出一个
????????char?c?=?tem[step];
????????if(c=='0')?c='B';
????????else?c='I';
????????ret+=c;
????????step++;
????????return?c;
????}
}
int?main(){
????cin>>num;
????cin>>tem;
????tree(num);
cout<<ret;
????return?0;
}
|