【NOIP2004普及组题三】FBI树【树的遍历】描述我们可以把由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;由左
#include <iostream>
#include <string>
using namespace std;
// 递归构造FBI树
string constructFBITree(string s) {
// 如果字符串长度为1,则直接返回对应的结点类型
if (s.length() == 1) {
if (s == "0") {
return "B";
} else {
return "I";
}
}
// 分割字符串
int mid = s.length() / 2;
string leftStr = s.substr(0, mid);
string rightStr = s.substr(mid);
// 构造左右子树
string leftTree = constructFBITree(leftStr);
string rightTree = constructFBITree(rightStr);
// 根据左右子树的类型确定根结点的类型
if (leftTree == rightTree) {
return leftTree;
} else {
return "F";
}
}
// 后序遍历FBI树
void postOrderTraversal(string tree, string& result) {
if (tree.length() == 1) {
result += tree;
return;
}
int mid = tree.length() / 2;
string leftTree = tree.substr(0, mid);
string rightTree = tree.substr(mid);
postOrderTraversal(leftTree, result);
postOrderTraversal(rightTree, result);
result += tree;
}
int main() {
int N;
string s;
cin >> N >> s;
string tree = constructFBITree(s);
string result = "";
postOrderTraversal(tree, result);
cout << result << endl;
return 0;
}
``
原文地址: https://gggwd.com/t/topic/hRWc 著作权归作者所有。请勿转载和采集!